Distance-based Subdivision for Translational LP Containment
Karen Daniels, Victor Milenkovic · 1996
The two-dimensional translational containment problem is to find translations for a collection of polygons which place them inside a polygonal container without overlapping. The polygons and container may be nonconvex. Our linear-programming-based (LP) translational containment algorithm uses our restrict /evaluate/subdivide paradigm which operates on two-dimensional configuration spaces. The following distance-based subdivision problem arises during the subdivision step: given a polygon U and a point t which is outside U but inside the convex hull of U , find the line L through t which partitions U into two pieces U \\Gamma and U + on opposite sides of L such that: min(\\Delta(t; CH(U \\Gamma )); \\Delta(t; CH(U + ))) is maximized, where CH(U) is the convex hull of U and \\Delta(a; B) is the Euclidean distance from a point a to a point set B. We show that if U is connected, then the distance-based subdivision problem can be solved in O(jU j) time in a real arithmetic model and in ...