Space searching for intersecting objects

David P. Dobkin; Herbert Edelsbrunner

doi:10.1016/0196-6774(87)90015-0

Space searching for intersecting objects

David P. Dobkin, Herbert Edelsbrunner

Research output: Contribution to journal › Article › peer-review

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 language	English (US)
Pages (from-to)	348-361
Number of pages	14
Journal	Journal of Algorithms
Volume	8
Issue number	3
DOIs	https://doi.org/10.1016/0196-6774(87)90015-0
State	Published - Sep 1987

All Science Journal Classification (ASJC) codes

Control and Optimization
Computational Mathematics
Computational Theory and Mathematics

Access to Document

10.1016/0196-6774(87)90015-0

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

Cite this

@article{16579b43f82f442ea73e005a9bce9697,

title = "Space searching for intersecting objects",

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.",

author = "Dobkin, {David P.} and Herbert Edelsbrunner",

year = "1987",

month = sep,

doi = "10.1016/0196-6774(87)90015-0",

language = "English (US)",

volume = "8",

pages = "348--361",

journal = "Journal of Algorithms",

issn = "0196-6774",

publisher = "Academic Press Inc.",

number = "3",

}

TY - JOUR

T1 - Space searching for intersecting objects

AU - Dobkin, David P.

AU - Edelsbrunner, Herbert

PY - 1987/9

Y1 - 1987/9

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=38249034526&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=38249034526&partnerID=8YFLogxK

U2 - 10.1016/0196-6774(87)90015-0

DO - 10.1016/0196-6774(87)90015-0

M3 - Article

AN - SCOPUS:38249034526

VL - 8

SP - 348

EP - 361

JO - Journal of Algorithms

JF - Journal of Algorithms

SN - 0196-6774

IS - 3

ER -