**Reference**:- Erik D. Demaine, John Iacono, and Stefan Langerman, “Proximate Point Searching”,
*Computational Geometry: Theory and Applications*, volume 28, number 1, May 2004, pages 29–40. Special issue of selected papers from the 14th Canadian Conference on Computational Geometry, 2002. **Abstract**:-
In the 2D point searching problem, the goal is to preprocess
*n*points*P*= {*p*_{1}, …,*p*_{n}} in the plane so that, for an online sequence of query points*q*_{1}, …,*q*_{m}, it can quickly determined which (if any) of the elements of*P*are equal to each query point*q*_{i}. This problem can be solved in*O*(log*n*) time by mapping the problem to one dimension. We present a data structure that is optimized for answering queries quickly when they are geometrically close to the previous successful query. Specifically, our data structure executes queries in time*O*(log*d*(*q*_{i−1},*q*_{i})), where*d*is some distance function between two points, and uses*O*(*n*log*n*) space. Our structure works with a variety of distance functions. In contrast, it is proved that, for some of the most intuitive distance functions*d*, it is impossible to obtain an*O*(log*d*(*q*_{i−1},*q*_{i})) runtime, or any bound that is*o*(log*n*). **Comments**:- This paper is also available from ScienceDirect.
**Length**:- The paper is 15 pages.
**Availability**:- The paper is available in PostScript (438k), gzipped PostScript (168k), and PDF (171k).
- See information on file formats.
- [Google Scholar search]
**Related papers**:- PointSearching_CCCG2002 (Proximate Point Searching)

See also other papers by Erik Demaine.

Last updated June 13, 2024 by Erik Demaine.