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

Abstract

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.

41 pages. Extensive clean-up of minor English errors

Cited by in corpus (21)

• Demand-Aware Network Designs of Bounded Degree
• New Constructions of SSPDs and their Applications
• Fast Clustering with Lower Bounds: No Customer too Far, No Shop too Small
• Greedy Strategy Works for $k$-Center Clustering with Outliers and Coreset Construction
• A light metric spanner
• Optimal Euclidean spanners: really short, thin and lanky
• Towards Metric DBSCAN: Exact, Approximate, and Streaming Algorithms
• Sublinear data structures for short Fréchet queries
• Nearly optimal classification for semimetrics
• Linear-Size Approximations to the Vietoris-Rips Filtration
• Locally Private k-Means in One Round
• Near-linear time approximation schemes for Steiner tree and forest in low-dimensional spaces
• A Composable Coreset for k-Center in Doubling Metrics
• Linear-Size Universal Discretization of Geometric Center-Based Problems in Fixed Dimensions
• Fast C-K-R Partitions of Sparse Graphs
• Faster Clustering via Preprocessing
• Sharp finiteness principles for Lipschitz selections: long version
• Local Doubling Dimension of Point Sets
• Algorithmic interpretations of fractal dimension
• How to Complete a Doubling Metric
• Optimal Approximate Distance Oracle for Planar Graphs