Fast Construction of Nets in Low Dimensional Metrics, and Their Applications

Details Fast Construction of Nets in Low Dimensional Metrics, and Their Applications Fast Construction of Nets in Low Dimensional Metrics, and Their Applications

2004-09-29

arxiv.org/abs/cs/0409057v3

SIAM J. Comput. 35(5):1148-1184, 2006

Computer Science

Data Structures and Algorithms

41 pages. Extensive clean-up of minor English errors

Scientific paper

10.1137/S0097539704446281

We present a near linear time algorithm for constructing hierarchical nets in finite metric spaces with constant doubling dimension. This data-structure is then applied to obtain improved algorithms for the following problems: Approximate nearest neighbor search, well-separated pair decomposition, compact representation scheme, doubling measure, and computation of the (approximate) Lipschitz constant of a function. In all cases, the running (preprocessing) time is near-linear and the space being used is linear.

Affiliated with

Also associated with

No associations

Rating

Fast Construction of Nets in Low Dimensional Metrics, and Their Applications 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 Construction of Nets in Low Dimensional Metrics, and Their Applications, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fast Construction of Nets in Low Dimensional Metrics, and Their Applications will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-23528