authors 
Nievergelt, J. and Preparata, Franco P. 
year 
1982 
title 
PlaneSweep Algorithms for Intersecting Geometric Figures 
source 
Communications of the ACM. October, 1982. vol. 25: pp. 739747 : ill. includes bibliography 
summary 
Algorithms in computational geometry are of increasing importance in computeraided design, for example, in the layout of integrated circuits. The efficient computation of the intersection of several superimposed figures is a basic problem. Plane figures defined by points connected by straight line segments are considered, 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 m be the total number of points of all the figures involved and s be the total number of intersections of all line segments. A two planesweep algorithm that solves the problems above is presented; in the general case (non convexity) in time O((n+s)logn) 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) 
keywords 
computational geometry, algorithms, intersection, mapping, polygons, data structures, analysis 
series 
CADline 
references 
Contenttype: text/plain

last changed 
2003/06/02 08:24 
