Abstract
We give an algorithm for bichromatic line segment in- tersection counting that runs in O(n √ log n) time under the word RAM model via a reduction to dynamic prede- cessor search, offline point location, and offline dynamic ranking. This algorithm is the first to solve bichromatic line segment intersection counting in o(n log n) time.
Original language | English (US) |
---|---|
State | Published - 2011 |
Externally published | Yes |
Event | 23rd Annual Canadian Conference on Computational Geometry, CCCG 2011 - Toronto, ON, Canada Duration: Aug 10 2011 → Aug 12 2011 |
Other
Other | 23rd Annual Canadian Conference on Computational Geometry, CCCG 2011 |
---|---|
Country/Territory | Canada |
City | Toronto, ON |
Period | 8/10/11 → 8/12/11 |
ASJC Scopus subject areas
- Computational Mathematics
- Geometry and Topology