Arrangements of curves in the plane --- topology, combinatorics, and algorithms (Q1185003): Difference between revisions

The goal of the paper is the generalization of some results about arrangements of lines to arrangements of curves under some mild assumptions on the shape of curves. An important property of arrangements of lines is the so-called zone theorem: Let \(A\) be an arrangement of \(n\) lines and let \(l\) be another line. Then the total number of edges bounding the faces of \(A\) that intersect \(l\) is \(O(n)\). The collection of these edges is the zone of \(l\) in \(A\). The authors show that the combinatorial complexity of the zone of a curve is nearly linear in the number of curves. An application of this result to obtain a nearly quadratic incremental algorithm for the construction of such arrangements is obtained. Also a new proof of the zone theorem is given.