Hopcroft's Problem, Log-Star Shaving, 2D Fractional Cascading, and Decision Trees

Timothy M. Chan, Da Wei Zheng

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We revisit Hopcroft's problem and related fundamental problems about geometric range searching. Given n points and n lines in the plane, we show how to count the number of point-line incidence pairs or the number of point-above-line pairs in O(n4=3) time, which matches the conjectured lower bound and improves the best previous time bound of n4=32O(log n) obtained almost 30 years ago by Matousek. We describe two interesting and different ways to achieve the result: the first is randomized and uses a new 2D version of fractional cascading for arrangements of lines; the second is deterministic and uses decision trees in a manner inspired by the sorting technique of Fredman (1976). The second approach extends to any constant dimension. Many consequences follow from these new ideas: for example, we obtain an O(n4=3)-time algorithm for line segment intersection counting in the plane, O(n4=3)-time randomized algorithms for bichromatic closest pair and Euclidean minimum spanning tree in three or four dimensions, and a randomized data structure for halfplane range counting in the plane with O(n4=3) preprocessing time and space and O(n1=3) query time.

Original languageEnglish (US)
Title of host publicationACM-SIAM Symposium on Discrete Algorithms, SODA 2022
PublisherAssociation for Computing Machinery
Pages190-210
Number of pages21
ISBN (Electronic)9781611977073
StatePublished - 2022
Event33rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2022 - Alexander, United States
Duration: Jan 9 2022Jan 12 2022

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
Volume2022-January

Conference

Conference33rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2022
Country/TerritoryUnited States
CityAlexander
Period1/9/221/12/22

ASJC Scopus subject areas

  • Software
  • General Mathematics

Fingerprint

Dive into the research topics of 'Hopcroft's Problem, Log-Star Shaving, 2D Fractional Cascading, and Decision Trees'. Together they form a unique fingerprint.

Cite this