Efficient dynamic algorithms for some geometric intersection problems

Siu Wing Cheng, Ravi Janardan

Research output: Contribution to journalArticlepeer-review

12 Scopus citations


Efficient dynamic algorithms are presented for four geometric intersection problems. These include: (1) reporting the subset of a set S of nonintersecting segments in the plane that are intersected by a query segment of fixed slope; (2) reporting the segments of S that are intersected by a query segment whose supporting line passes through a fixed point; (3) the orthogonal segment intersection search problem; and (4) the point enclosure problem for isothetic hyper-rectangles in d-dimensional space, d ≥ 2. These algorithms are the first linear-space solutions to Problems 1-3 and for Problem 4 in the plane. For Problem 3, the update time improves upon the previous best algorithm by a logarithmic factor without affecting the query time. For Problem 4, the update time either matches or improves upon the previous best algorithms, but the query time is larger by a logarithmic factor. No dynamic algorithms were known previously for Problems 1 and 2.

Original languageEnglish (US)
Pages (from-to)251-258
Number of pages8
JournalInformation Processing Letters
Issue number5
StatePublished - Dec 1 1990

Bibliographical note

Funding Information:
* Research supported in part by a grant-in-aid of research from the Graduate School of the University of Minnesota. The second author was also supported in part by NSF grant CCR-8808574.


  • Analysis of algorithms
  • computational complexity
  • computational geometry
  • data structures
  • design of algorithms


Dive into the research topics of 'Efficient dynamic algorithms for some geometric intersection problems'. Together they form a unique fingerprint.

Cite this