---
res:
bibo_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).@eng
bibo_authorlist:
- foaf_Person:
foaf_givenName: Herbert
foaf_name: Herbert Edelsbrunner
foaf_surname: Edelsbrunner
foaf_workInfoHomepage: http://www.librecat.org/personId=3FB178DA-F248-11E8-B48F-1D18A9856A87
orcid: 0000-0002-9823-6833
- foaf_Person:
foaf_givenName: Leonidas
foaf_name: Guibas, Leonidas J
foaf_surname: Guibas
- foaf_Person:
foaf_givenName: Micha
foaf_name: Sharir, Micha
foaf_surname: Sharir
bibo_doi: ' 10.1007/BF02187784'
bibo_issue: '1'
bibo_volume: 5
dct_date: 1990^xs_gYear
dct_publisher: Springer@
dct_title: The complexity and construction of many faces in arrangements of lines
and of segments@
...