Fast Construction of Nets in Low-Dimensional Metrics and Their Applications
From MaRDI portal
Publication:5470729
DOI10.1137/S0097539704446281zbMath1100.68014MaRDI QIDQ5470729
Manor Mendel, Sariel Har-Peled
Publication date: 1 June 2006
Published in: SIAM Journal on Computing (Search for Journal in Brave)
quadtreedoubling measuredoubling dimensionnearest neighbor searchdistance labelingapproximate distance oraclemetric nets
Analysis of algorithms (68W40) Searching and sorting (68P10) Packing and covering in (n) dimensions (aspects of discrete geometry) (52C17) Data structures (68P05) Approximation algorithms (68W25)
Related Items (75)
On Locality-Sensitive Orderings and Their Applications ⋮ Linear-size universal discretization of geometric center-based problems in fixed dimensions ⋮ The Minimum Moving Spanning Tree Problem ⋮ The minimum moving spanning tree problem ⋮ Pattern matching in doubling spaces ⋮ ANN for time series under the Fréchet distance ⋮ Routing on heavy-path WSPD-spanners ⋮ Algorithms for graphs of bounded treewidth via orthogonal range searching ⋮ Sharp finiteness principles for Lipschitz selections ⋮ Dvoretzky-type theorem for Ahlfors regular spaces ⋮ Space exploration via proximity search ⋮ Fitting a \(C^m\)-smooth function to data. III. ⋮ Linear-size approximations to the Vietoris-Rips filtration ⋮ Covering metric spaces by few trees ⋮ Multiscale geometric methods for data sets. I: Multiscale SVD, noise and curvature. ⋮ Near isometric terminal embeddings for doubling metrics ⋮ Demand-aware network designs of bounded degree ⋮ A nonlinear approach to dimension reduction ⋮ An introduction to the Ribe program ⋮ Relaxed spanners for directed disk graphs ⋮ Making doubling metrics geodesic ⋮ New constructions of SSPDs and their applications ⋮ Approximation schemes for \(k\)-facility location ⋮ Additive spanners and distance and routing labeling schemes for hyperbolic graphs ⋮ Computing the Greedy Spanner in Near-Quadratic Time ⋮ Low-interference networks in metric spaces of bounded doubling dimension ⋮ Embedding snowflakes of Carnot groups into bounded dimensional Euclidean spaces with optimal distortion ⋮ Maximum gradient embeddings and monotone clustering ⋮ Online Spanners in Metric Spaces ⋮ Geometric spanners for weighted point sets ⋮ Unnamed Item ⋮ Spanners for geodesic graphs and visibility graphs ⋮ Distance estimation and object location via rings of neighbors ⋮ Approximate nearest neighbor search for \(\ell_{p}\)-spaces \((2 < p < \infty)\) via embeddings ⋮ Computing the greedy spanner in near-quadratic time ⋮ Unnamed Item ⋮ Using the doubling dimension to analyze the generalization of learning algorithms ⋮ Space-Time Tradeoffs for Proximity Searching in Doubling Spaces ⋮ An Optimal Dynamic Spanner for Doubling Metric Spaces ⋮ A new approach to output-sensitive construction of Voronoi diagrams and Delaunay triangulations ⋮ Geodesic spanners for points in \(\mathbb{R}^3\) amid axis-parallel boxes ⋮ Efficient subspace approximation algorithms ⋮ Coresets for the Nearest-Neighbor Rule ⋮ On Locality-Sensitive Orderings and Their Applications ⋮ Linear-Space Approximate Distance Oracles for Planar, Bounded-Genus and Minor-Free Graphs ⋮ Space-efficient path-reporting approximate distance oracles ⋮ Small hop-diameter sparse spanners for doubling metrics ⋮ Recovering the long-range links in augmented graphs ⋮ The jet of an interpolant on a finite set ⋮ Shortest-path queries in static networks ⋮ Geodesic Spanners for Points on a Polyhedral Terrain ⋮ Snowflake universality of Wasserstein spaces ⋮ Ramsey partitions and proximity data structures ⋮ Measuring sample quality with diffusions ⋮ Fractal dimension and lower bounds for geometric problems ⋮ The Greedy Spanner Is Existentially Optimal ⋮ Greedy Strategy Works for k-Center Clustering with Outliers and Coreset Construction ⋮ Unnamed Item ⋮ Local embeddings of metric spaces ⋮ Fitting a \(C^m\)-smooth function to data. II ⋮ The \(C^m\) norm of a function with prescribed jets. II ⋮ Non-uniform packings ⋮ Covering Metric Spaces by Few Trees ⋮ Approximating Distance Measures for the Skyline ⋮ The Weak Gap Property in Metric Spaces of Bounded Doubling Dimension ⋮ Local routing in a tree metric \(1\)-spanner ⋮ Near Isometric Terminal Embeddings for Doubling Metrics ⋮ Light spanners for high dimensional norms via stochastic decompositions ⋮ Economical Delone Sets for Approximating Convex Bodies ⋮ Embedding Metrics into Ultrametrics and Graphs into Spanning Trees with Constant Average Distortion ⋮ Metric Spaces with Expensive Distances ⋮ On Some Proximity Problems of Colored Sets ⋮ Self-organizing Flows in Social Networks ⋮ Near-neighbor preserving dimension reduction via coverings for doubling subsets of \(\ell_1\) ⋮ Low dimensional embeddings of doubling metrics
This page was built for publication: Fast Construction of Nets in Low-Dimensional Metrics and Their Applications
