ISSN:
1439-6912
Keywords:
52 B 05
;
52 C 10
;
68 U 05
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
Notes:
Abstract We show that the maximum number of edges boundingm faces in an arrangement ofn line segments in the plane isO(m 2/3 n 2/3+nα(n)+nlogm). This improves a previous upper bound of Edelsbrunner et al. [5] and almost matches the best known lower bound which is Ω(m 2/3 n 2/3+nα(n)). In addition, we show that the number of edges bounding anym faces in an arrangement ofn line segments with a total oft intersecting pairs isO(m 2/3 t 1/3+nα(t/n)+nmin{logm,logt/n}), almost matching the lower bound of Ω(m 2/3 t 1/3+nα(t/n)) demonstrated in this paper.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01285815
Permalink