UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Intersecting red and blue line segments in optimal time and precision Mantler, Andrea


In this thesis we describe a new algorithm, SPAGHETTISWEEP, for solving the red-blue line segment intersection problem. We use a symmetric lazy sweep and at most degree two predicates. Our method is numerically robust, and handles all degeneracies in the input data. Our algorithm finds all intersecting pairs of segments in O(n log n + k) time and O(n) space, where n is the total number of segments, and k is the number of intersection points. With a small modification, we are able to count intersections in O(n log n) time and O(n) space. Using only degree two predicates, we are also able to compute the arrangement in O(n log n + k) time.

Item Media

Item Citations and Data


For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use.

Usage Statistics