Deformable spanners and applications
From MaRDI portal
Publication:2507157
DOI10.1016/j.comgeo.2005.10.001zbMath1102.65024OpenAlexW2208163925WikidataQ41148146 ScholiaQ41148146MaRDI QIDQ2507157
Publication date: 10 October 2006
Published in: Computational Geometry (Search for Journal in Brave)
Full work available at URL: http://europepmc.org/articles/pmc3001688
Voronoi diagramcollision detectionkinetic data structuresclosest pairwell-separated pair decompositionkinetic algorithmsapproximate nearest neighborgeometric \(k\)-centerproximity maintenancespanner graphs
Numerical aspects of computer graphics, image analysis, and computational geometry (65D18) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
Kinetic clustering of points on the line ⋮ Linear-size approximations to the Vietoris-Rips filtration ⋮ Topological stability of kinetic \(k\)-centers ⋮ Near isometric terminal embeddings for doubling metrics ⋮ Minimum weight Euclidean \((1+\varepsilon)\)-spanners ⋮ Relaxed spanners for directed disk graphs ⋮ Minimum weight Euclidean \((1+\varepsilon)\)-spanners ⋮ Online Spanners in Metric Spaces ⋮ Kinetic Maintenance of Mobile k-Centres on Trees ⋮ Light Euclidean Spanners with Steiner Points ⋮ Optimal nearest neighbor queries in sensor networks ⋮ A simple and efficient kinetic spanner ⋮ Kinetic spanners in \(\mathbb R^{d}\) ⋮ Kinetic facility location ⋮ Approximation algorithm for the kinetic robust \(k\)-center problem ⋮ Unnamed Item ⋮ The Traveling Salesman Problem: Low-Dimensionality Implies a Polynomial Time Approximation Scheme ⋮ Fully dynamic geometric spanners ⋮ Kinetic maintenance of mobile \(k\)-centres on trees ⋮ Minimizing Co-location Potential of Moving Entities ⋮ On the Impossibility of Dimension Reduction for Doubling Subsets of $\ell_{p}$ ⋮ Local routing in a tree metric \(1\)-spanner ⋮ Near Isometric Terminal Embeddings for Doubling Metrics
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Collision detection for deforming necklaces
- Clustering to minimize the maximum intercluster distance
- Sphere packings give an explicit bound for the Besicovitch covering theorem
- Discrete mobile centers
- Efficient construction of a bounded-degree spanner with low weight
- An optimal algorithm for approximate nearest neighbor searching fixed dimensions
- Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
- Space-efficient approximate Voronoi diagrams
- ENUMERATING INTERDISTANCES IN SPACE
- SIMPLE ALGORITHMS FOR ENUMERATING INTERPOINT DISTANCES AND FINDING k NEAREST NEIGHBORS
- Data Structures for Mobile Data
- A decomposition of multidimensional point sets with applications to k -nearest-neighbors and n -body potential fields
- Approximating the Stretch Factor of Euclidean Graphs
- Distributed Computing: A Locality-Sensitive Approach
- Efficient maintenance and self-collision testing for Kinematic Chains
- SEQUENTIAL AND PARALLEL ALGORITHMS FOR THE k CLOSEST PAIRS PROBLEM
- Smooth kinetic maintenance of clusters
- Improved algorithms for constructing fault-tolerant spanners
