TCS Journal 2026 Journal Article
Largest similar copies of convex polygons in polygonal domains
- Taekang Eom
- Seungjun Lee
- Hee-Kap Ahn
Given a convex polygon with k vertices and a polygonal domain consisting of polygonal obstacles with n vertices in total in the plane, we study the optimization problem of finding a largest similar copy of the polygon that can be placed in the polygonal domain without intersecting the obstacles. We present an upper bound O(k 2 n 2 λ 4(k)) on the number of combinatorial changes occurring to the underlying structure during the rotation of the polygon, together with an O(k 2 n 2 λ 4(k)log n)-time deterministic algorithm for the problem, where λs (n) is the length of the longest Davenport–Schinzel sequence of order s including n distinct symbols. This improves upon the previously best known results by Chew and Kedem [SoCG89, CGTA93] and Sharir and Toledo [SoCG91, CGTA94] on the problem in more than 27 years. Our result also improves the time complexity of the high-clearance motion planning algorithm by Chew and Kedem.