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

Timothy M. Chan, Bryan T. Wilkinson

Research output: Contribution to conferencePaperpeer-review

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 - 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
Country/TerritoryCanada
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