Paper by Erik D. Demaine

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.

In the 2D point searching problem, the goal is to preprocess n points P = {p1, …, pn} in the plane so that, for an online sequence of query points q1, …, qm, it can quickly determined which (if any) of the elements of P are equal to each query point qi. 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(qi−1qi)), 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(qi−1qi)) runtime, or any bound that is o(log n).

This paper is also available from ScienceDirect.

The paper is 15 pages.

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.
These pages are generated automagically from a BibTeX file.
Last updated October 16, 2017 by Erik Demaine.