Open Collections

Intersecting red and blue line segments in optimal time and precision

University of British Columbia

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.

Thesis/Dissertation

application/pdf

2009-08-06

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.

http://hdl.handle.net/2429/11868

Computer Science

University of British Columbia

UBCV

DSpace