Space Searching For Intersecting Objects

25 August 2005

conference paper
Published by Institute of Electrical and Electronics Engineers (IEEE)

p. 387-392
https://doi.org/10.1109/sfcs.1984.715939

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, plaraes, and polyhedra in three dimensions.

Keywords

This publication has 6 references indexed in Scilit:

On k-hulls and related problems
Published by Association for Computing Machinery (ACM) ,1984
A 3-space partition and its applications
Published by Association for Computing Machinery (ACM) ,1983
Polygonal intersection searching
Information Processing Letters, 1982
Polygon Retrieval
SIAM Journal on Computing, 1982
Decomposable searching problems
Information Processing Letters, 1979
Organization and maintenance of large ordered indexes
Acta Informatica, 1972