Affordable Access

Some applications of the topological plane sweep algorithm

McGill University
Publication Date
  • Computer Science.
  • Computer Science
  • Mathematics


The arrangements of lines stand at the heart of many problems in Computational Geometry, and the topological plane sweep algorithm (EG 86) permits to visit these structures in optimal time and space. This algorithm already improved the resolution of several older problems. In this thesis we present new applications where visiting an arrangement plays a major role. In the first we resolve the problem of finding the points contained on a line from each of k sets of n lines in O(kn$ sp2$) time and O(kn) space. In the second the task is to find the lines that can intersect (or stab) one element from each of k sets. The sets contain line segments or polygons, and the algorithm uses O(k$ sp2$n$ sp2$) time and O(k$ sp2$n) space, where n is the total size of the elements in each set. Minor modifications to the algorithm published in (EG 86) are also described. They allow the handling of degeneracies without recourse to a perturbation technique.

There are no comments yet on this publication. Be the first to share your thoughts.