Geometric range searching
- 1 December 1994
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Computing Surveys
- Vol. 26 (4) , 422-461
- https://doi.org/10.1145/197405.197408
Abstract
In geometric range searching, algorithmic problems of the following type are considered. Given ann-point set P in the plane, build a data structure so that, given a query triangle R, the number of points of P lying in R can be determined quickly. Similar questions can be asked for point sets in higher dimensions, with triangles replaced by simplices or by more complicated shapes. Algorithms of this type are of crucial importance in computational geometry, as they can be used as subroutines in solutions to many seemingly unrelated problems, which are often motivated by practical applications, for instance in computer graphics (ray tracing, hidden-surface removal etc.). We present a survey of theoretical results and the main techniques in geometric range searching.Keywords
This publication has 83 references indexed in Scilit:
- On range searching with semialgebraic setsDiscrete & Computational Geometry, 1994
- Counting Circular Arc IntersectionsSIAM Journal on Computing, 1993
- Ray Shooting and Parametric SearchSIAM Journal on Computing, 1993
- Selecting distances in the planeAlgorithmica, 1993
- On the zone of a surface in a hyperplane arrangementDiscrete & Computational Geometry, 1993
- Applications of a new space-partitioning techniqueDiscrete & Computational Geometry, 1993
- Partitioning arrangements of lines II: ApplicationsDiscrete & Computational Geometry, 1990
- Partitioning and geometric embedding of range spaces of finite Vapnik-Chervonenkis dimensionPublished by Association for Computing Machinery (ACM) ,1987
- Non-partitionable point setsInformation Processing Letters, 1984
- Multidimensional divide-and-conquerCommunications of the ACM, 1980