Largest similar copies of convex polygons amidst polygonal obstacles

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^2{n}^2{\lambda }_4(k)\log n)$. 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.