ZIB

Hits per page

hit 1 - 1 | 1 hit

Sorting

Electronic Resource

The number of edges of many faces in a line segment arrangement (1992)

Aronov, B. ; Edelsbrunner, H. ; Guibas, L. J. ; [et al.]

Springer

Combinatorica 12 (1992), S. 261-274

add to mindlist on the mindlist

Details

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

Library	Location	Call Number	Volume/Issue/Year	Availability

Others were also interested in ...

Paper (German National Licenses)

Fulltext

hit 1 - 1 | 1 hit