## Abstract

In the 2D point searching problem, the goal is to preprocess n points P={p _{1},⋯,p _{n}} in the plane so that, for an online sequence of query points q _{1},⋯,q _{m}, it can quickly be determined which (if any) of the elements of P are equal to each query point q _{i}. This problem can be solved in O(logn) 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(logd(q _{i-1},q _{i})), where d is some distance function between two points, and uses O(nlogn) 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(logd(q _{i-1}, q _{i})) runtime, or any bound that is o(logn).

Original language | English (US) |
---|---|

Pages (from-to) | 29-40 |

Number of pages | 12 |

Journal | Computational Geometry: Theory and Applications |

Volume | 28 |

Issue number | 1 |

DOIs | |

State | Published - May 2004 |

## Keywords

- Distance functions
- Dynamic finger property
- Point location

## ASJC Scopus subject areas

- Computer Science Applications
- Geometry and Topology
- Control and Optimization
- Computational Theory and Mathematics
- Computational Mathematics