**Reference**:- Erik D. Demaine, John Iacono, and Stefan Langerman, “Proximate Point Searching”, in
*Proceedings of the 14th Canadian Conference on Computational Geometry (CCCG 2002)*, Lethbridge, Alberta, Canada, August 12–14, 2002, pages 1–4. **Abstract**:-
In the 2D point searching problem, our 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}, we can quickly determine 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 down 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},*q*_{i−1})), where*d*is some distance metric between two points. Our structure works with a variety of distance metrics. In contrast, we prove that, for some of the most intuitive distance metrics*d*, it is impossible to obtain an*O*(log*d*(*q*_{i},*q*_{i−1})) runtime, or any bound that is*o*(log*n*). **Comments**:- This paper is also available from the electronic proceedings as http://www.cs.uleth.ca/~wismath/cccg/papers/22.ps.
**Length**:- The paper is 4 pages.
**Availability**:- The paper is available in PostScript (165k), gzipped PostScript (61k), and PDF (124k).
- See information on file formats.
- [Google Scholar search]
**Related papers**:- PointSearching_CGTA (Proximate Point Searching)

See also other papers by Erik Demaine.

Last updated March 26, 2017 by Erik Demaine.