Space searching for intersecting objects

David P. Dobkin, Herbert Edelsbrunner

Research output: Contribution to journalArticlepeer-review

34 Scopus citations


Determining or counting geometric objects that intersect another geometric query object is at the core of algorithmic problems in a number of applied areas of computer science. This article presents a family of space-efficient data structures that realize sublinear query time for points, line segments, lines and polygons in the plane, and points, line segments, planes, and polyhedra in three dimensions.

Original languageEnglish (US)
Pages (from-to)348-361
Number of pages14
JournalJournal of Algorithms
Issue number3
StatePublished - Sep 1987

All Science Journal Classification (ASJC) codes

  • Control and Optimization
  • Computational Mathematics
  • Computational Theory and Mathematics


Dive into the research topics of 'Space searching for intersecting objects'. Together they form a unique fingerprint.

Cite this