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

2017/06/09 by Yoav Kallus, Kallus, Yoav
Computer Science · #52B55 #65D18 #68Q25 #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #FOS: Computer and information sciences #FOS: Mathematics #Metric Geometry (math.MG)

paper · pdf · doi:10.48550/arxiv.1706.03049

openalex publication_date 2017/06/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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öffler, 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.

Related

• Linear time Minimum Area All-flush Triangles Circumscribing a Convex Polygon
• On implementation of the minimal perimeter triangle enclosing a convex polygon algorithm
• The Largest Contained Quadrilateral and the Smallest Enclosing\n Parallelogram of a Convex Polygon
• A technique for solving the polygon inclusion problems
• An algorithm to find maximum area polygons circumscribed about a convex\n polygon