Maximum-Area Triangle in a Convex Polygon, Revisited

We revisit the following problem: Given a convex polygon P, find the largest-area inscribed triangle. We prove by counterexample that the linear-time algorithm presented in 1979 by Dobkin and Snyder [5] for solving this problem fails, as well as a renewed analysis of the problem. We also provide a counterexample proving that their algorithm fails finding the largest-area inscribed quadrilateral. Combined with the work in [2], [3], it follows that the algorithm is incorrect for all possible values of k.

Journal Article (peer-reviewed)

Archived Publication (not reviewed)

back to list