论文标题
在多边形障碍物中最大的凸多边形的类似副本
Largest similar copies of convex polygons amidst polygonal obstacles
论文作者
论文摘要
给定带有$ k $顶点的凸多边形$ P $和多边形域$ q $由多边形障碍物组成，总尺寸$ n $在飞机上，我们研究了可以找到可以将$ p $的最大类似副本放入$ q $的优化问题。我们提高了解决问题的时间复杂性到$ O（k^2n^2λ_4（k）\ log {n}）$。这是改善Chew and Kedem [SocG89，CGTA93]和Sharir和Sharir和Toledo [SOCG91，CGTA94]的进展。
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)\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.
