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
Fingerprint
Dive into the research topics of 'Bichromatic line segment intersection counting in O(n √ log n) time'. Together they form a unique fingerprint.Cite this
- APA
- Standard
- Harvard
- Vancouver
- Author
- BIBTEX
- RIS