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.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom