On the Union of Cylinders in Three Dimensions
Esther E. Ezra · 2008
We show that the combinatorial complexity of the union of n infinite cylinders in R3, having arbitrary radii, is O(n2+epsiv), for any epsiv >0; the bound is almost tight in the worst case, thus settling a conjecture of Agarwal and Sharir, who established a nearly-quadratic bound for the restricted case of nearly congruent cylinders. Our result extends, in a significant way, the result of Agarwal and Sharir, in particular, a simple specialization of our analysis to the case of nearly congruent cylinders yields a nearly-quadratic bound on the complexity of the union in that case, thus significantly simplifying the analysis in. Finally, we extend our technique to the case of "cigars'' of arbitrary radii (that is, Minkowski sums of line-segments and balls), and show that the combinatorial complexity of the union in this case is nearly-quadratic as well. This problem has been studied in for the restricted case where all cigars are (nearly) equal-radii. Based on our new approach, the proof follows almost verbatim from the analysis for infinite cylinders, and is significantly simpler than the proof presented in [3].