|
Published Articles >> Table of Contents >> Abstract
The 43rd Annual IEEE Symposium on Foundations of Computer Science (FOCS'02)
p. 637
The Partition Technique for Overlays of Envelopes
Vladlen Koltun, Tel Aviv University
Micha Sharir, Tel Aviv University
Full Article Text:
  
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/SFCS.2002.1181989
Send link to a friend
| Abstract |
|
We obtain a near-tight bound of 0(n^{3 + \varepsilon }), for any \varepsilon > 0, on the complexity of the overlay of the minimization diagrams of two collections of surfaces in four dimensions. This settles a long-standing problem in the theory of arrangements, most recently cited by Agarwal and Sharir [3, Open Problem 2], and substantially improves and simplifies a result previously published by the authors [15]. Our bound has numerous algorithmic and combinatorial applications, some of which are presented in this paper. Our result is obtained by introducing a new approach to the analysis of combinatorial structures arising in geometric arrangements of surfaces. This approach, which we call the ‘partition technique’, is based on k-fold divide and conquer, in which a given collection F of n surfaces is partitioned into k subcollections Fi of {n \mathord{\left/ {\vphantom {n k}} \right. \kern-\nulldelimiterspace} k} surfaces each, and the complexity of the relevant combinatorial structure in F is recursively related to the complexities of the corresponding structures in each of the Fi’s. We introduce this approach by applying it first to obtain a new simple proof for the known near-quadratic bound on the complexity of an overlay of two minimization diagrams of collections of surfaces in \mathbb{R}^3, thereby simplifying the previously available proof [2].
|
 Additional Information
|
Citation:
Vladlen Koltun, Micha Sharir,
"The Partition Technique for Overlays of Envelopes,"
focs,
p. 637,
The 43rd Annual IEEE Symposium on Foundations of Computer Science (FOCS'02),
2002
|
|
