Plane-sweep algorithms for intersecting geometric figures

Algorithms in computational geometry are of increasing importace in computer-aided design, for example, in the layout of integrated circuits. The efficient computation of the intersection of several superimposed figures is a basic problem. We consider plane figures defined by points connected by straight line segments, for example, polygons (not necessarily simple) and maps (embedded planar graphs). The regions into which the plane is partitioned by these intersecting figures are to be processed in various ways such as listing the boundary of each region in cyclic order or sweeping the interior of each region. Let n be the total number of points of all the figures involved and s be the total number of intersections of all line segments. We present two planesweep algorithms that solve the problems above; in the general case (no convexity) in time O((n + s)log n) and space O(n + s); when the regions of each given figure are convex, the same can be achieved in time O(n log n + s) and space O(n).