Paper by Erik D. Demaine

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.

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

This paper is also available from the electronic proceedings as

The paper is 4 pages.

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