Extremal convex polygons inscribed in a given convex polygon

2021/01/08 by Ködmön, Csenge Lili, Lángi, Zsolt
#52A38 #52B60 #68W01 #Combinatorics (math.CO) #FOS: Mathematics #Metric Geometry (math.MG)

paper · doi:10.48550/arxiv.2101.03061

Abstract

A convex polygon Q is inscribed in a convex polygon P if every side of P contains at least one vertex of Q. We present algorithms for finding a minimum area and a minimum perimeter convex polygon inscribed in any given convex n-gon in O(n) and O(n³) time, respectively. We also investigate other variants of this problem.

Related

• An algorithm to find maximum area polygons circumscribed about a convex\n polygon
• Finding Largest Rectangles in Convex Polygons
• Convex Polygon Containment: Improving Quadratic to Near Linear Time
• A linear-time algorithm for the maximum-area inscribed triangle in a convex polygon
• A technique for solving the polygon inclusion problems