@article{4102, 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 and Edelsbrunner, Herbert}, issn = {1090-2678}, journal = {Journal of Algorithms}, number = {3}, pages = {348 -- 361}, publisher = {Academic Press}, title = {{Space searching for intersecting objects}}, doi = {10.1016/0196-6774(87)90015-0}, volume = {8}, year = {1987}, }