Paper by Erik D. Demaine

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 = {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).

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