Open Collections will undergo scheduled maintenance on the following dates: On Monday, April 27th, 2026, the site will not be available from 7:00 AM – 9:00 AM PST and on Tuesday, April 28th, 2026, the site will remain accessible from 7:00 AM – 9:00 AM PST, however item images and media will not be available during this time.
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Intersecting red and blue line segments in optimal...
Open Collections
UBC Theses and Dissertations
UBC Theses and Dissertations
Intersecting red and blue line segments in optimal time and precision Mantler, Andrea
Abstract
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 Metadata
| Title |
Intersecting red and blue line segments in optimal time and precision
|
| Creator | |
| Publisher |
University of British Columbia
|
| Date Issued |
2001
|
| Description |
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.
|
| Extent |
3194392 bytes
|
| Genre | |
| Type | |
| File Format |
application/pdf
|
| Language |
eng
|
| Date Available |
2009-08-06
|
| Provider |
Vancouver : University of British Columbia Library
|
| Rights |
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.
|
| DOI |
10.14288/1.0051494
|
| URI | |
| Degree (Theses) | |
| Program (Theses) | |
| Affiliation | |
| Degree Grantor |
University of British Columbia
|
| Graduation Date |
2001-11
|
| Campus | |
| Scholarly Level |
Graduate
|
| Aggregated Source Repository |
DSpace
|
Item Media
Item Citations and Data
Rights
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.