Name
Abstract | ||
|---|---|---|
We revisit the following problem: Given a convex polygon $P$, find the largest-area inscribed triangle. We show by example that the linear-time algorithm presented in 1979 by Dobkin and Snyder for solving this problem fails. We then proceed to show that with a small adaptation, their approach does lead to a quadratic-time algorithm. We also present a more involved $O(nlog n)$ time divide-and-conquer algorithm. Also we show by example that the algorithm presented in 1979 by Dobkin and Snyder for finding the largest-area $k$-gon that is inscribed in a convex polygon fails to find the optimal solution for $k=4$. Finally, we discuss the implications of our discoveries on the literature. |
Year | Venue | Field |
|---|---|---|
2017 | arXiv: Computational Geometry | Binary logarithm,Discrete mathematics,Combinatorics,Polygon covering,Inscribed figure,Krein–Milman theorem,Convex polygon,Mathematics |
DocType | Volume | Citations |
Journal | abs/1705.11035 | 1 |
PageRank | References | Authors |
0.48 | 11 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Vahideh Keikha | 1 | 1 | 2.85 |
| Maarten Löffler | 2 | 551 | 62.87 |
| Jérôme Urhausen | 3 | 1 | 2.17 |
| Ivor van der Hoog | 4 | 1 | 2.51 |