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.

BibTeX

@InProceedings{PointSearching_CCCG2002,
  AUTHOR        = {Erik D. Demaine and John Iacono and Stefan Langerman},
  TITLE         = {Proximate Point Searching},
  BOOKTITLE     = {Proceedings of the 14th Canadian Conference on Computational
                   Geometry (CCCG 2002)},
  bookurl       = {http://www.cs.uleth.ca/cccg},
  ADDRESS       = {Lethbridge, Alberta, Canada},
  MONTH         = {August 12--14},
  YEAR          = 2002,
  PAGES         = {1--4},

  award         = {Invited to special issue of \emph{Computational Geometry: Theory and Applications}.},
  length        = {4 pages},
  comments      = {This paper is also available from the
                   <A HREF="http://www.cs.uleth.ca/~wismath/cccg/proceedings/">
                   electronic proceedings</A> as
                   <A HREF="http://www.cs.uleth.ca/~wismath/cccg/papers/22.ps">http://www.cs.uleth.ca/~wismath/cccg/papers/22.ps</A>, and from <A HREF="https://doi.org/10.1016/j.comgeo.2004.01.005">ScienceDirect</A>.},
  PAPERS        = {PointSearching_CGTA},
  unrefereed    = 1
}

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, and from ScienceDirect.

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)