Publication Details
Title: Building Convex Space Partitions Induced by Pairwise Interior-Disjoint Simplices
Author: M. Pellegrini
Group: ICSI Technical Reports
Date: August 1993
PDF: ftp://ftp.icsi.berkeley.edu/pub/techreports/1993/tr-93-039.pdf
Overview:
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.
Bibliographic Information:
ICSI Technical Report TR-93-039
Bibliographic Reference:
M. Pellegrini. Building Convex Space Partitions Induced by Pairwise Interior-Disjoint Simplices. ICSI Technical Report TR-93-039, August 1993
Author: M. Pellegrini
Group: ICSI Technical Reports
Date: August 1993
PDF: ftp://ftp.icsi.berkeley.edu/pub/techreports/1993/tr-93-039.pdf
Overview:
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.
Bibliographic Information:
ICSI Technical Report TR-93-039
Bibliographic Reference:
M. Pellegrini. Building Convex Space Partitions Induced by Pairwise Interior-Disjoint Simplices. ICSI Technical Report TR-93-039, August 1993