Fast, precise and dynamic distance queries

Details Fast, precise and dynamic distance queries Fast, precise and dynamic distance queries

2010-08-09

arxiv.org/abs/1008.1480v1

Computer Science

Data Structures and Algorithms

Scientific paper

We present an approximate distance oracle for a point set S with n points and doubling dimension {\lambda}. For every {\epsilon}>0, the oracle supports (1+{\epsilon})-approximate distance queries in (universal) constant time, occupies space [{\epsilon}^{-O({\lambda})} + 2^{O({\lambda} log {\lambda})}]n, and can be constructed in [2^{O({\lambda})} log3 n + {\epsilon}^{-O({\lambda})} + 2^{O({\lambda} log {\lambda})}]n expected time. This improves upon the best previously known constructions, presented by Har-Peled and Mendel. Furthermore, the oracle can be made fully dynamic with expected O(1) query time and only 2^{O({\lambda})} log n + {\epsilon}^{-O({\lambda})} + 2^{O({\lambda} log {\lambda})} update time. This is the first fully dynamic (1+{\epsilon})-distance oracle.

Affiliated with

Also associated with

No associations

Rating

Fast, precise and dynamic distance queries does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Fast, precise and dynamic distance queries, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fast, precise and dynamic distance queries will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-83571