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−1, qi)),
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−1, qi))
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 July 23, 2024 by
Erik Demaine.