TY - JOUR
T1 - Space searching for intersecting objects
AU - Dobkin, David P.
AU - Edelsbrunner, Herbert
N1 - Funding Information:
*This work was performed while the first author Was visiting at the Technical University of Graz during May and June 1983. tResearch of this author was supported in part by the National Science Foundation under Grant MCS83-03926 and DCRg5-05517. *Research of this author was supported by the Austrian Fonds zur Foerderung der wissenschaftlichen Forschung. Present address: Department of Computer Science, University of Illinois, Urbana, Illinois 61801.
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 -