Euclidean spanners: short, thin, and lanky

No abstract is available for this paper.

• Publication year

  1995

• Venue

  Symposium on the Theory of Computing

• Publication date

  1995-05-29

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1145/225058.225191
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• A data structure for dynamically maintaining rooted trees

  1997cited by this paper
• A decomposition of multidimensional point sets with applications to k-nearest-neighbors and n-body potential fields

  1995cited by this paper
• A new way to weigh Malnourished Euclidean graphs

  1995cited by this paper
• Randomized and deterministic algorithms for geometric spanners of small diameter

  1994cited by this paper
• A fast algorithm for constructing sparse Euclidean spanners

  1994cited by this paper
• Optimally sparse spanners in 3-dimensional Euclidean space

  1993cited by this paper
• Faster algorithms for some geometric graph problems in higher dimensions

  1993cited by this paper
• A decomposition of multi-dimensional point-sets with applications to k-nearest-neighbors and n-body potential fields (preliminary version)

  1992cited by this paper
• New sparseness results on graph spanners

  1992cited by this paper
• Constructing multidimensional spanner graphs

  1991cited by this paper
• A sparse graph almost as good as the complete graph on points inK dimensions

  1991influential reference

• Euclidean Noncrossing Steiner Spanners of Nearly Optimal Sparsity

  2026cites this paper
• Spanning and Metric Tree Covers Parameterized by Treewidth

  2025cites this paper
• Near-Optimal Dynamic Steiner Spanners for Constant-Curvature Spaces

  2025cites this paper
• Lower Bounds on Tree Covers

  2025cites this paper
• Covering Approximate Shortest Paths with DAGs

  2025cites this paper
• A Unified Framework of Light Spanners I: Fast (Yet Optimal) Constructions

  2025cites this paper
• Tree-Like Shortcuttings of Trees

  2025cites this paper
• Light Tree Covers, Routing, and Path-Reporting Oracles via Spanning Tree Covers in Doubling Graphs

  2025cites this paper
• Light Spanners with Small Hop-Diameter

  2025influential citation
• Tree covers of size 2 for the Euclidean plane

  2025cites this paper
• A Tight Lower Bound for Doubling Spanners

  2025cites this paper
• Metric Sketching and Dynamic Algorithms for Geometric and Topological Graphs (Dagstuhl Seminar 25212)

  2025influential citation
• A WSPD, Separator and Small Tree Cover for c-packed Graphs

  2025cites this paper
• Covering the Euclidean Plane by a Pair of Trees

  2025cites this paper
• Optimal Euclidean Tree Covers

  2024cites this paper
• The Complexity of Geodesic Spanners using Steiner Points

  2024cites this paper
• Highway Dimension: a Metric View

  2024cites this paper
• Embeddings and near-neighbor searching with constant additive error for hyperbolic spaces

  2024cites this paper
• A well-separated pair decomposition for low density graphs

  2024cites this paper
• Dynamic Locality Sensitive Orderings in Doubling Metrics

  2024cites this paper
• An O(n log n)-Time Approximation Scheme for Geometric Many-to-Many Matching

  2024cites this paper
• The Complexity of Geodesic Spanners

  2023cites this paper
• Optimal Fault-Tolerant Spanners in Euclidean and Doubling Metrics: Breaking the Ω (log n) Lightness Barrier

  2023cites this paper
• Sparse Euclidean Spanners with Optimal Diameter: A General and Robust Lower Bound via a Concave Inverse-Ackermann Function

  2023cites this paper
• Constant-Hop Spanners for More Geometric Intersection Graphs, with Even Smaller Size

  2023cites this paper
• D-Lite: Navigation-Oriented Compression of 3D Scene Graphs under Communication Constraints

  2022cites this paper
• D-Lite: Navigation-Oriented Compression of 3D Scene Graphs for Multi-Robot Collaboration

  2022cites this paper
• Vertex Fault-Tolerant Spanners for Weighted Points in Polygonal Domains

  2021cites this paper
• 1 4 M ay 2 01 5 A light metric spanner

  2021cites this paper
• Local Algorithms for Bounded Degree Sparsifiers in Sparse Graphs

  2021cites this paper
• Greedy Spanners in Euclidean Spaces Admit Sublinear Separators

  2021cites this paper
• Towards a Unified Theory of Light Spanners I: Fast (Yet Optimal) Constructions

  2021cites this paper
• Reliable Spanners: Locality-Sensitive Orderings Strike Back

  2021cites this paper
• Can't See the Forest for the Trees: Navigating Metric Spaces by Bounded Hop-Diameter Spanners

  2021influential citation
• Locality-sensitive orderings and applications to reliable spanners

  2021cites this paper
• Sparse Euclidean Spanners with Tiny Diameter: A Tight Lower Bound

  2021cites this paper
• On Hop-Constrained Steiner Trees in Tree-Like Metrics

  2020cites this paper
• Computing a Minimum-Cost k-hop Steiner Tree in Tree-Like Metrics

  2020cites this paper
• A Unified Framework for Light Spanners

  2020cites this paper
• Local routing in a tree metric 1-spanner

  2020cites this paper
• Vertex Fault-Tolerant Geometric Spanners for Weighted Points

  2020cites this paper
• Covering Metric Spaces by Few Trees

  2019influential citation
• Approximating APSP without scaling: equivalence of approximate min-plus and exact min-max

  2019influential citation
• Geodesic Fault-Tolerant Additive Weighted Spanners

  2019cites this paper
• Graph Spanners: A Tutorial Review

  2019cites this paper
• Truly Optimal Euclidean Spanners

  2019cites this paper
• Faster Algorithms for the Geometric Transportation Problem

  2019cites this paper
• Handbook of Approximation Algorithms and Metaheuristics Contemporary and Emerging Applications

  2019influential citation
• Nearest Neighbor Distances

  2017cites this paper
• Exact computation of a manifold metric, via Lipschitz Embeddings and Shortest Paths on a Graph

  2017cites this paper
• Local Routing in Spanners Based on WSPDs

  2017cites this paper
• Fault-Tolerant Additive Weighted Geometric Spanners

  2017cites this paper
• Greedy spanners are optimal in doubling metrics

  2017cites this paper
• 8 LOW-DISTORTION EMBEDDINGS OF FINITE METRIC SPACES

  2017cites this paper
• Intrinsic Metrics: Exact Equality between a Geodesic Metric and a Graph metric

  2017cites this paper
• 32 PROXIMITY ALGORITHMS

  2016cites this paper
• Geometric Spanners

  2016cites this paper
• A Light Metric Spanner

  2015cites this paper
• Optimal Euclidean Spanners

  2015cites this paper
• Title : Geometric Spanners Name :

  2014cites this paper
• Light Spanners

  2014cites this paper
• Light spanners for Snowflake Metrics

  2014cites this paper
• Spanning Properties of Theta-Theta Graphs

  2014cites this paper
• Sparsification of motion-planning roadmaps by edge contraction

  2014cites this paper
• New Doubling Spanners: Better and Simpler

  2013influential citation
• From hierarchical partitions to hierarchical covers: optimal fault-tolerant spanners for doubling metrics

  2013influential citation
• Efficient Construction of Spanners in $d$-Dimensions

  2013cites this paper
• Sparse Euclidean Spanners with Tiny Diameter

  2013influential citation
• Property testing in gradbeschränkten gerichteten Graphen unter Nichtsichtbarkeit eingehender Kanten

  2013cites this paper
• Robust geometric spanners

  2012cites this paper
• Sparse Fault-Tolerant Spanners for Doubling Metrics with Bounded Hop-Diameter or Degree

  2012influential citation
• Incubators vs Zombies: Fault-Tolerant, Short, Thin and Lanky Spanners for Doubling Metrics

  2012cites this paper
• Optimal euclidean spanners: really short, thin and lanky

  2012influential citation
• Spanners for geometric intersection graphs with applications

  2012cites this paper
• Fault-Tolerant Spanners for Doubling Metrics: Better and Simpler

  2012cites this paper
• The emergence of sparse spanners and well-separated pair decomposition under anarchy

  2012cites this paper
• Near-Linear-Time Deterministic Plane Steiner Spanners and TSP Approximation for Well-Spaced Point Sets

  2012cites this paper
• Near-linear-time deterministic plane Steiner spanners for well-spaced point sets

  2012cites this paper
• Notes on Binary Dumbbell Trees

  2012cites this paper
• Sparsification of motion-planning roadmaps by edge contraction

  2012cites this paper
• Title Sparse Fault-Tolerant Spanners for Doubling Metrics withBounded Hop-Diameter or Degree

  2012cites this paper
• Approximating Minimum Manhattan Networks in Higher Dimensions

  2011cites this paper
• Steiner Shallow-Light Trees are Exponentially Lighter than Spanning Ones

  2011cites this paper
• The traveling salesman problem: low-dimensionality implies a polynomial time approximation scheme

  2011cites this paper
• Approximation Techniques for Facility Location and Their Applications in Metric Embeddings

  2011cites this paper
• Data : f Client Query : x f ( x ) Data : f Client Filter Query : x g

  2011cites this paper
• An optimal-time construction of sparse Euclidean spanners with tiny diameter

  2011cites this paper
• Balancing Degree, Diameter, and Weight in Euclidean Spanners

  2011influential citation
• Algorithms and Models for Problems in Networking

  2010cites this paper
• Balancing Degree, Diameter and Weight in Euclidean Spanners

  2010influential citation
• Pruning spanners and constructing well-separated pair decompositions in the presence of memory hierarchies

  2010cites this paper
• Lower Bounds for Local Monotonicity Reconstruction from Transitive-Closure Spanners

  2010cites this paper
• An Optimal-Time Construction of Euclidean Sparse Spanners with Tiny Diameter

  2010influential citation
• Testing Euclidean Spanners

  2010cites this paper
• An optimal algorithm for computing angle-constrained spanners

  2010influential citation
• Cross-Layer Design for Wireless Networks Using Antenna Arrays

  2009cites this paper
• Geodesic Spanners on Polyhedral Surfaces

  2009cites this paper
• Narrow-Shallow-Low-Light Trees with and without Steiner Points

  2009cites this paper
• The Emergence of Sparse Spanners and Greedy Well-Separated Pair Decomposition

  2009cites this paper
• Topology Management in Directional Antenna-Equipped Ad Hoc Networks

  2009cites this paper