Bichromatic line segment intersection counting in O(n √ log n) time

Timothy Moon-Yew Chan, Bryan T. Wilkinson

Research output: Contribution to conferencePaper

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 languageEnglish (US)
StatePublished - Dec 1 2011
Externally publishedYes
Event23rd Annual Canadian Conference on Computational Geometry, CCCG 2011 - Toronto, ON, Canada
Duration: Aug 10 2011Aug 12 2011

Other

Other23rd Annual Canadian Conference on Computational Geometry, CCCG 2011
CountryCanada
CityToronto, ON
Period8/10/118/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

    Chan, T. M-Y., & Wilkinson, B. T. (2011). Bichromatic line segment intersection counting in O(n √ log n) time. Paper presented at 23rd Annual Canadian Conference on Computational Geometry, CCCG 2011, Toronto, ON, Canada.