Largest similar copies of convex polygons amidst polygonal obstacles

2020/12/13 by Eom, Taekang, Lee, Seungjun, Ahn, Hee-Kap
#Computational Geometry (cs.CG) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2012.06978

Abstract

Given a convex polygon P with k vertices and a polygonal domain Q consisting of polygonal obstacles with total size n in the plane, we study the optimization problem of finding a largest similar copy of P that can be placed in Q without intersecting the obstacles. We improve the time complexity for solving the problem to O(k²n²λ₄(k)logn). This is progress of improving the previously best known results by Chew and Kedem [SoCG89, CGTA93] and Sharir and Toledo [SoCG91, CGTA94] on the problem in more than 25 years.

Related

• Convex Polygon Containment: Improving Quadratic to Near Linear Time
• Finding Largest Rectangles in Convex Polygons
• Polygon Placement Revisited: (Degree of Freedom + 1)-SUM Hardness and an Improvement via Offline Dynamic Rectangle Union
• Large k-gons in a 1.5D Terrain
• The Largest Contained Quadrilateral and the Smallest Enclosing\n Parallelogram of a Convex Polygon