Space searching for intersecting objects

David P. Dobkin, Herbert Edelsbrunner

Research output: Contribution to journalArticle

33 Scopus citations

Abstract

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
Volume8
Issue number3
DOIs
StatePublished - Sep 1987

All Science Journal Classification (ASJC) codes

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

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

  • Cite this