A linear-time algorithm for the maximum-area inscribed triangle in a convex polygon

Yoav Kallus

Given the n vertices of a convex polygon in cyclic order, can the triangle of maximum area inscribed in P be determined by an algorithm with O(n) time complexity? A purported linear-time algorithm by Dobkin and Snyder from 1979 has recently been shown to be incorrect by Keikha, L\"offler, Urhausen, and van der Hoog. These authors give an alternative algorithm with O(n log n) time complexity. Here we give an algorithm with linear time complexity.

Knowledge Graph

arrow_drop_up

Comments

Sign up or login to leave a comment