Largest similar copies of convex polygons amidst polygonal obstacles

12/13/2020
by   Taekang Eom, et al.
0

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

Please sign up or login with your details

Forgot password? Click here to reset