DocumentCode :
3217924
Title :
The partition technique for overlays of envelopes
Author :
Koltun, Vladlen ; Sharir, Micha
Author_Institution :
Sch. of Comput. Sci., Tel Aviv Univ., Israel
fYear :
2002
fDate :
2002
Firstpage :
637
Lastpage :
646
Abstract :
We obtain a near-tight bound of O(n3+ε), for any ε > 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 (2000), and substantially improves and simplifies a result previously published by the authors (2002). 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 ℱ of n surfaces is partitioned into k subcollections ℱi of n/k surfaces each, and the complexity of the relevant combinatorial structure in ℱ is recursively related to the complexities of the corresponding structures in each of the ℱi´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 R3, thereby simplifying the previously available proof (1996).
Keywords :
combinatorial mathematics; computational complexity; computational geometry; divide and conquer methods; algorithmic applications; combinatorial applications; combinatorial structures; geometric arrangements; k-fold divide and conquer; minimization diagrams; near-quadratic bound; near-tight bound; partition technique; Computer science; Geometry; Polynomials;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Foundations of Computer Science, 2002. Proceedings. The 43rd Annual IEEE Symposium on
ISSN :
0272-5428
Print_ISBN :
0-7695-1822-2
Type :
conf
DOI :
10.1109/SFCS.2002.1181989
Filename :
1181989
Link To Document :
بازگشت