Largest similar copies of convex polygons amidst polygonal obstacles
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^2n^2λ_4(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.
READ FULL TEXT