Maximum-Area Triangle in a Convex Polygon, Revisited

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(n\log 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.

References in corpus (3)

• A linear-time algorithm for the maximum-area inscribed triangle in a convex polygon
• Inextensible domains
• The Largest Contained Quadrilateral and the Smallest Enclosing Parallelogram of a Convex Polygon

Cited by in corpus (5)

• A linear-time algorithm for the maximum-area inscribed triangle in a convex polygon
• The Largest Contained Quadrilateral and the Smallest Enclosing Parallelogram of a Convex Polygon
• Largest Inscribed Rectangles in Geometric Convex Sets
• Finding all Maximal Area Parallelograms in a Convex Polygon
• Maximum-Area Quadrilateral in a Convex Polygon, Revisited