---
res:
bibo_abstract:
- Arrangements of curves in the plane are of fundamental significance in many problems
of computational and combinatorial geometry (e.g. motion planning, algebraic cell
decomposition, etc.). In this paper we study various topological and combinatorial
properties of such arrangements under some mild assumptions on the shape of the
curves, and develop basic tools for the construction, manipulation, and analysis
of these arrangements. Our main results include a generalization of the zone theorem
of [EOS], [CGL] to arrangements of curves (in which we show that the combinatorial
complexity of the zone of a curve is nearly linear in the number of curves), and
an application of (some weaker variant of) that theorem to obtain a nearly quadratic
incremental algorithm for the construction of such arrangements.@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
foaf_surname: Guibas
- foaf_Person:
foaf_givenName: János
foaf_name: Pach, János
foaf_surname: Pach
- foaf_Person:
foaf_givenName: Richard
foaf_name: Pollack, Richard
foaf_surname: Pollack
- foaf_Person:
foaf_givenName: Raimund
foaf_name: Seidel, Raimund
foaf_surname: Seidel
- foaf_Person:
foaf_givenName: Micha
foaf_name: Sharir, Micha
foaf_surname: Sharir
bibo_doi: 10.1007/3-540-19488-6_118
bibo_volume: 317
dct_date: 1988^xs_gYear
dct_publisher: Springer@
dct_title: Arrangements of curves in the plane - topology, combinatorics, and algorithms@
...