Plane-sweep algorithms for intersecting geometric figures

Abstract

Algorithms in computational geometry are of increas- ing importace in computer-aided design, for example, in the layout of integrated circuits. The efficient computa- tion 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 pro- cessed 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 inter- sections of all line segments. We present two plane- sweep 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).