Paper by Erik D. Demaine

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₁, …, p_n} in the plane so that, for an online sequence of query points q₁, …, 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)