Building Convex Space Partitions Induced by Pairwise Interior-Disjoint Simplices
| Title | Building Convex Space Partitions Induced by Pairwise Interior-Disjoint Simplices |
| Publication Type | Technical Report |
| Year of Publication | 1993 |
| Authors | Pellegrini, M. |
| Other Numbers | 827 |
| Abstract | Given a set S of n pairwise interior-disjoint (d-1)-simplices in d-space, for d ? 3, a Convex Space Partition induced by S (denoted CSP(S)) is a partition of d-space into convex cells such that the interior of each cell does not intersect the interior of any simplex in S. In this paper it is shown that a CSP(S) of size O(n^{d-1}) can be computed deterministically in time O(n^{d-1}). These bounds are worst case optimal for d=3. The results are proved using a variation of the efficient hierarchical cuttings of Chazelle. |
| URL | http://www.icsi.berkeley.edu/ftp/global/pub/techreports/1993/tr-93-039.pdf |
| Bibliographic Notes | ICSI Technical Report TR-93-039 |
| Abbreviated Authors | M. Pellegrini |
| ICSI Publication Type | Technical Report |