The complexity and construction of many faces in arrangements of lines and of segments |
| |
Authors: | Herbert Edelsbrunner Leonidas J Guibas Micha Sharir |
| |
Institution: | (1) Department of Computer Science, University of Illinois at Urbana-Champaign, 61801 Urbana, Ill, USA;(2) DEC Systems Research Center, 130 Lytton Avenue Palo Alto, 94301, Ca, USA;(3) Department of Computer Science, Stanford University, 94305, Ca, USA;(4) Courant Institute of Mathematical Sciences, New York University, 10012 New York, NY, USA;(5) School of Mathematical Science, Tel Aviv University, 69978 Tel Aviv, Israel |
| |
Abstract: | We show that the total number of edges ofm faces of an arrangement ofn lines in the plane isO(m
2/3–
n
2/3+2
+n) for any >0. The proof takes an algorithmic approach, that is, we describe an algorithm for the calculation of thesem faces and derive the upper bound from the analysis of the algorithm. The algorithm uses randomization and its expected time complexity isO(m
2/3–
n
2/3+2
logn+n logn logm). If instead of lines we have an arrangement ofn line segments, then the maximum number of edges ofm faces isO(m
2/3–
n
2/3+2
+n (n) logm) for any >0, where (n) is the functional inverse of Ackermann's function. We give a (randomized) algorithm that produces these faces and takes expected timeO(m
2/3–
n
2/3+2
log+n (n) log2
n logm).The first author is pleased to acknowledge partial support by the Amoco Fnd. Fac. Dev. Comput. Sci. 1-6-44862 and the National Science Foundation under Grant CCR-8714565. Work on this paper by the third author has been supported by Office of Naval Research Grant N00014-82-K-0381, by National Science Foundation Grant DCR-83-20085, by grants from the Digital Equipment Corporation, and the IBM Corporation, and by a research grant from the NCRD-the Israeli National Council for Research and Development. A preliminary version of this paper has appeared in theProceedings of the 4th ACM Symposium on Computational Geometry, 1988, pp. 44–55. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|