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.

BibTeX

@Article{PointSearching_CGTA,
  AUTHOR        = {Erik D. Demaine and John Iacono and Stefan Langerman},
  TITLE         = {Proximate Point Searching},
  JOURNAL       = {Computational Geometry: Theory and Applications},
  journalurl    = {https://www.sciencedirect.com/journal/computational-geometry},
  VOLUME        = 28,
  NUMBER        = 1,
  MONTH         = {May},
  YEAR          = {2004},
  PAGES         = {29--40},
  NOTE          = {Special issue of selected papers from the 14th Canadian
                   Conference on Computational Geometry, 2002.},

  length        = {15 pages},
  papers        = {PointSearching_CCCG2002},
  replaces      = {PointSearching_CCCG2002},
  doi           = {https://dx.doi.org/10.1016/J.COMGEO.2004.01.005},
  dblp          = {https://dblp.org/rec/journals/comgeo/DemaineIL04},
  comments      = {This paper is also available from
                   <A HREF="http://dx.doi.org/10.1016/j.comgeo.2004.01.005">ScienceDirect</A>.},
}

Abstract:

In the 2D point searching problem, the 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, it can quickly determined 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 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−1, q_i)), 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(q_i−1, q_i)) 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)