z-logo
open-access-imgOpen Access
The union of congruent cubes in three dimensions
Author(s) -
János Pach,
Ido Safruti,
Micha Sharir
Publication year - 2001
Publication title -
citeseer x (the pennsylvania state university)
Language(s) - English
Resource type - Conference proceedings
DOI - 10.1145/378583.378598
Subject(s) - dihedral angle , mathematics , combinatorics , wedge (geometry) , alpha (finance) , geometry , solid angle , mathematical analysis , physics , optics , quantum mechanics , hydrogen bond , construct validity , statistics , molecule , detector , psychometrics
A {\em dihedral (trihedral) wedge} is the intersection of two (resp. t hree) half-spaces in $\reals^3$. It is called {\em $\alpha$-fat} if the angle (resp., solid angle) determined by these half-spaces is at least $\alpha>0$. If, in addition, the sum of the three face angles of a trihedral wedge is at least $\gamma >4\pi/3$, then it is called {\em $(\gamma,\alpha)$-substantially fat}. We prove that, for any fixed $\gamma>4\pi/3, \alpha>0$, the combinatorial complexity of the union of $n$ (a) $\alpha$-fat dihedral wedges, (b) $(\gamma,\alpha)$-substantially fat trihedral wedges is at most $O(n^{2+\eps})$, for any $\eps>0$, where the constants of proportionality depend on $\eps$, $\alpha$ (and $\gamma$).We obtain as a corollary that the same upper bound holds for the combinatorial complexity of the union of $n$ (nearly) congruent cubes in $\reals^3$. These bounds are not far from being optimal.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.
Having issues? You can contact us here
Accelerating Research

Address

John Eccles House
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom