Given n line segments in the plane, the Bentley-Ottmann sweep maintains the exact ordering of the intersections of the segments with a vertical line, as this line sweeps the plane from left to right. To accomplish this, every intersection between two segments must be processed, and the running time of the sweep can be \\Omega\\Gamma n 2 ). In this paper, it is shown how a heap on the intersections can be maintained during the sweep. This new type of sweep processes O(n log 2 n) intersections when sweeping over lines and O(n p n log n) intersections when sweeping over line segments. A lower bound of \\Omega\\Gamma n log n) is also established. 1 Introduction One of the common introductory problems in geometric algorithms is that of finding all pairwise intersections in a family of line segments in the plane. The first nontrivial solution to this problem was given by Bentley and Ottmann [BO79], who introduced in 1979 the now familiar line sweep paradigm. A vertical line is moved (`swe...

We use the concept of the convolution of two polygons as a tool for computing the outer-face of their Minkowski sum. Our method consists of traversing each cycle of the convolution, detecting selfintersections, and snipping-off the loops thus created. In order to detect self-intersections, we adapt the geodesic triangulation ray-shooting data structure to answer ray-shooting queries on a dynamic polygonal line of size n, in O(log 2 n) amortized time. We find the outer-face of the Minkowski sum of two simple polygons of size m and n respectively in time O((k+(m+n) p l) log 2 (m+n)) where k is the size of the convolution and l is the number of cycles in the convolution. Although k can be O(mn) in the worst case, it is much less for realistic input instances. If one of the polygons is convex, then the convolution has only one cycle, and the algorithm runs in O(k log 2 (m + n)) time. Existing methods to find the Minkowski sum outer-face rely on general algorithms to compute a si...