An O(kN.log N) algorithm for decomposing a set of polygons into d-separable components

摘要

Given a set of polygons P = {P1,P2,…,PN} in the plane, a D-separable component with respect to a given set of directions D = {d1,d2,…,dk} is a subset of polygons Q ⊆ P which can be moved freely as a group in any of the directions D without colliding with any polygon not in Q. We present an O(kN.log N) algorithm for computing the D-separable components of a set of N polygons. The algorithm is based on the concept of D-closure defined here and can be viewed as a certain orderly application of the well-known plane-sweep method to specially formed subgroups of polygons. An improper choice of the order of the plane-sweep operations or of the subgroups of polygons can increase the complexity to O(N2) in the worst case. The notion of separable components is useful for partitioning the free space in VLSI design and for motion planning in robotics.