Aarhus University Seal / Aarhus Universitets segl

Bryan T. Wilkinson

Bichromatic Line Segment Intersection Counting in O(n sqrt{log n}) Time

Research output: Contribution to conferencePaperResearchpeer-review

We give an algorithm for bichromatic line segment intersection counting that runs in O(n sqrt{log n}) time under the word RAM model via a reduction to dynamic predecessor 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 languageEnglish
Publication year2011
Number of pages5
Publication statusPublished - 2011
Externally publishedYes
EventCanadian Conference on Computational Geometry - , Canada
Duration: 8 May 20108 May 2010
Conference number: 23


ConferenceCanadian Conference on Computational Geometry

See relations at Aarhus University Citationformats

ID: 52483415