--- res: bibo_abstract: - Arrangements of curves in the plane are fundamental to many problems in 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 Edelsbrunner (1986) and Chazelle (1985) 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 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: Edelsbrunner, Herbert 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.1016/0304-3975(92)90319-B bibo_issue: '2' bibo_volume: 92 dct_date: 1992^xs_gYear dct_isPartOf: - http://id.crossref.org/issn/0304-3975 dct_language: eng dct_publisher: Elsevier@ dct_title: Arrangements of curves in the plane - topology, combinatorics, and algorithms@ ...