Translational polygon containment and minimal enclosure using linear programming based restriction
Victor Milenkovic · 1996
We introduce and analyze a new technique Linear Progmmming Based Restn"ction (LP Restriction) for solving translational containment and enclosure problems.The ~ontainment task is to translate k m-gons into a n-gon container.The enclosure task is to translate k m-gons into a minimum area n-gon which is convex with fixed orientation edges.All running times are based on an assumption of fixed k and are asymptotic in m and n.Lower bounds are roved for confk tainment in a nonconvex container: Q((mn) ) for nonconvex polygons and Cl (nk ) for convex polygons.LP restriction ac.Meves upper bound O ( (m2 + rnn)2k log n) for nonconvex polygons and O((mn)k log n) for convex polygons.