loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07)
Almost Tight Bound for the Union of Fat Tetrahedra in Three Dimensions
Providence, Rhode Island
October 21-October 23
ISBN: 0-7695-3010-9
We show that the combinatorial complexity of the union of n "fat" tetrahedra in 3-space (i.e., tetrahedra all of whose solid angles are at least some fixed constant) of arbitrary sizes, is {\rm O}(n^{2 + \varepsilon } ) for any \varepsilon \le 0; the bound is almost tight in the worst case, thus almost settling a conjecture of Pach et al. [24]. Our result extends, in a significant way, the result of Pach et al. [24] for the restricted case of nearly congruent cubes. The analysis uses cuttings, combined with the Dobkin-Kirkpatrick hierarchical decomposition of convex polytopes, in order to partition space into subcells, so that, on average, the overwhelming majority of the tetrahedra intersecting a subcell \vartriangle behave as fat dihedral wedges in \vartriangle. As an immediate corollary, we obtain that the combinatorial complexity of the union of n cubes in \mathbb{R}^3, having arbitrary side lengths, is {\rm O}(n^{2 + \varepsilon } ), for any \varepsilon \le 0 (again, significantly extending the result of [24]). Our analysis can easily be extended to yield a nearly-quadratic bound on the complexity of the union of arbitrarily oriented fat triangular prisms (whose cross-sections have arbitrary sizes) in \mathbb{R}^3. Finally, we show that a simple variant of our analysis implies a nearly-linear bound on the complexity of the union of fat triangles in the plane.
Citation:
Esther Ezra, Micha Sharir, "Almost Tight Bound for the Union of Fat Tetrahedra in Three Dimensions," focs, pp.525-535, 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07), 2007
Usage of this product signifies your acceptance of the Terms of Use.