We consider the problem of decomposing a 3D region into simple regions, which is an important problem in motion planning and solid modeling. Specifically, we consider the case where the 3D region is implicitly defined as the common exterior of a set of N axis-aligned cubes, and we wish to partition the common exterior into boxes with pairwise-disjoint interiors. Since the cubes may intersect, the combinatorial complexity K of the boundary of the union may be as small as O(1) and as large as O(N^2). Furthermore, K is a lower bound for the size of the smallest decomposition.
We present an algorithm to compute a decomposition of size O(K polylog N) in comparable time. For the case where all cubes are congruent, we present a simpler algorithm to compute a decomposition of size O(N log N). These results improve upon decompositions of size O(K^{3/2}) from previous work.
This talk is based on joint work with Pankaj K. Agarwal and Micha Sharir.
Forgot your password?
