Name
Abstract | ||
|---|---|---|
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 O(n2+epsiv),for any epsiv > 0: the bound is almost tight in the worst case, thus almost settling a conjecture of Pach el 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-K'irkpatrick 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 Delta behave as fat dihedral wedges in Delta. As an immediate corollary, we obtain that the combinatorial complexity of the union of n cubes in R3 having arbitrary side lengths, is O(n2+epsiv), for any epsiv > 0 again, significantly extending the result of [24]. Our analysis can easily he 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 R3. 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. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1109/FOCS.2007.10 | FOCS |
Keywords | Field | DocType |
rm o,dobkin-kirkpatrick hierarchical decomposition,almost tight bound,arbitrary side length,computational geometry,fat triangular prism,fat dihedral wedge,fat triangle,computational complexity,restricted case,three dimension,arbitrary size,n cube,worst case,combinatorial complexity,fat tetrahedra,cross section,three dimensions,convex polytope | Discrete mathematics,Combinatorics,Regular polygon,Polytope,Tetrahedron,Partition (number theory),Conjecture,Congruence (geometry),Dihedral angle,Mathematics,Cube | Conference |
ISSN | ISBN | Citations |
0272-5428 | 978-0-7695-3010-9 | 11 |
PageRank | References | Authors |
0.62 | 27 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Esther Ezra | 1 | 148 | 18.36 |
| Micha Sharir | 2 | 8405 | 1183.84 |