Searching dynamic point sets in spaces with bounded doubling dimension.pdf

Searching Dynamic Point Sets in Spaces with Bounded Doubling Dimension∗ Richard Cole Lee-Ad Gottlieb cole@cs.nyu.edu adi@cs.nyu.edu Courant Institute New York University New York, NY 10033 ABSTRACT within radius r of a point be called the ball centered at that We present a new data structure that facilitates approximate point. If point set X has doubling dimension λ, then all nearest neighbor searches on a dynamic set of points in a points of X that are covered by a ball of radius r can be covered by 2λ balls of radius r . A metric is doubling if its metric space that has a bounded doubling dimension. Our 2 data structure has linear size and supports insertions and dimension is O(1). While a low Euclidean dimension implies deletions in O(log n) time, and finds a (1 + ǫ)-approximate a low doubling dimension (Euclidean metrics of dimension O (1) d have doubling dimension O(d) [12]), low doubling dimen- nearest neighbor in time O(log n) + (1/ǫ) . The search sion is more general than low Euclidean dimension. For and update times hide