An algorithm to find maximum area polygons circumscribed about a convex\n polygon

2017/06/25 by Markus Ausserhofer, Ausserhofer, Markus, Susanna Dann +5
Computer Science · Engineering · #52A38 #52B60 #62H12 #68W01 #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #FOS: Mathematics #Metric Geometry (math.MG) #Optimization and Packing Problems #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.1706.08152

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

Abstract

A convex polygon Q is circumscribed about a convex polygon P if every vertex\nof P lies on at least one side of Q. We present an algorithm for finding a\nmaximum area convex polygon circumscribed about any given convex n-gon in\nO(n³) time. As an application, we disprove a conjecture of Farris. Moreover,\nfor the special case of regular n-gons we find an explicit solution.\n

Related

• Extremal convex polygons inscribed in a given convex polygon
• Maximum-Area Quadrilateral in a Convex Polygon, Revisited
• A technique for solving the polygon inclusion problems
• A linear-time algorithm for the maximum-area inscribed triangle in a convex polygon
• Finding Largest Rectangles in Convex Polygons