10.1007/3-540-19488-6_118
Herbert Edelsbrunner
Herbert
Edelsbrunner0000-0002-9823-6833
Guibas, Leonidas
Leonidas
Guibas
Pach, János
János
Pach
Pollack, Richard
Richard
Pollack
Seidel, Raimund
Raimund
Seidel
Sharir, Micha
Micha
Sharir
Arrangements of curves in the plane - topology, combinatorics, and algorithms
LNCS
Springer
1988
2018-12-11T12:06:55Z
2019-04-26T07:22:40Z
conference
https://research-explorer.app.ist.ac.at/record/4097
https://research-explorer.app.ist.ac.at/record/4097.json
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.