ABSTRACT
We study two problems involving collision-free place ments of a convex m-gon P in a planar polygonal envi ronment: (i) We first show that the largest similar copy of P inside another convex polygon Q with n edges can be computed in 0 (m n 2 log n) time. We also show that the combinatorial complexity of the space of all simi lar copies of P inside Q is 0 (m n 2), and that it can also be computed in 0 (m n 2 \ogn) time, (ii) We then consider the case where Q is an arbitrary polygonal en vironment with n edges. We give the first algorithm that constructs the entire free configuration space (the 3-dimensional space of all free placements of P in Q) in time that is near-quadratic in mn, which is nearly optimal in the worst case. The algorithm is also rela tively simple. Previous solutions of the second problem were either incomplete, more expensive, or produced only part of the free configuration space. Combining our solution with parametric searching, we obtain an algorithm that finds the largest placement of P in Q in time that is also near-quadratic in mn. In addition, we describe an algorithm that preprocesses the computed free configuration space so that ‘reachability’ queries can be answered in poly logarithmic time.
