Personal tools
You are here: Home CG seminar 2021 Decomposing the complement of the union of cubes
« December 2020 »
December
SuMoTuWeThFrSa
12345
6789101112
13141516171819
20212223242526
2728293031
Log in


Forgot your password?
 

Decomposing the complement of the union of cubes

Wednesday, January 6th, 16:10

underline

Alex Steiger, Duke University

Abstract:

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.

Document Actions