Cover Image

Towards Instance-Optimal Euclidean Spanners

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Le, Hung, Solomon, Shay, Than, Cuong, Tóth, Csaba D., Zhang, Tianyi
Format:	Preprint
Published:	2024
Subjects:	Computational Geometry Data Structures and Algorithms I.3.5
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Optimal Bounds for Spanners and Tree Covers in Doubling Metrics
by: La, An, et al.
Published: (2025)

Optimal Fault-Tolerant Spanners in Euclidean and Doubling Metrics: Breaking the $Ω(\log n)$ Lightness Barrier
by: Le, Hung, et al.
Published: (2023)

Approximate Light Spanners in Planar Graphs
by: Le, Hung, et al.
Published: (2025)

Greedy Spanners in Euclidean Spaces Admit Sublinear Separators
by: Le, Hung, et al.
Published: (2021)

Towards a Unified Theory of Light Spanners I: Fast (Yet Optimal) Constructions
by: Le, Hung, et al.
Published: (2021)

Spanners in Planar Domains via Steiner Spanners and non-Steiner Tree Covers
by: Bhore, Sujoy, et al.
Published: (2024)

The Marco Polo Problem: A Combinatorial Approach to Geometric Localization
by: Gila, Ofek, et al.
Published: (2025)

Tree-Like Shortcuttings of Trees
by: Le, Hung, et al.
Published: (2025)

The Presort Hierarchy for Geometric Problems
by: van der Hoog, Ivor, et al.
Published: (2026)

Light Tree Covers, Routing, and Path-Reporting Oracles via Spanning Tree Covers in Doubling Graphs
by: Chang, Hsien-Chih, et al.
Published: (2025)

Online Duet between Metric Embeddings and Minimum-Weight Perfect Matchings
by: Bhore, Sujoy, et al.
Published: (2023)

Approximating Euclidean Shallow-Light Trees
by: Le, Hung, et al.
Published: (2025)

The Complexity of Geodesic Spanners
by: de Berg, Sarita, et al.
Published: (2023)

The Maximum Clique Problem in a Disk Graph Made Easy
by: Keil, J. Mark, et al.
Published: (2024)

Light Spanners with Small Hop-Diameter
by: Bhore, Sujoy, et al.
Published: (2025)

Dynamic Light Spanners in Doubling Metrics
by: Bhore, Sujoy, et al.
Published: (2026)

Maintaining Light Spanners via Minimal Updates
by: Khodabandeh, Hadi, et al.
Published: (2024)

The Complexity of Geodesic Spanners using Steiner Points
by: de Berg, Sarita, et al.
Published: (2024)

Spanner for the $0/1/\infty$ weighted region problem
by: Gudmundsson, Joachim, et al.
Published: (2024)

On Optimal Coreset Construction for Euclidean $(k,z)$-Clustering
by: Huang, Lingxiao, et al.
Published: (2022)

Almost-Optimal Sublinear Additive Spanners
by: Tan, Zihan, et al.
Published: (2023)

Nearly Optimal Dynamic Set Cover: Breaking the Quadratic-in-$f$ Time Barrier
by: Bukov, Anton, et al.
Published: (2023)

Instance and Universally Optimal Bounds for Imprecise Pareto Fronts
by: de Berg, Sarita, et al.
Published: (2026)

Fine-Grained Complexity of Continuous Euclidean k-Center
by: Blank, Lotte, et al.
Published: (2026)

Dynamic Locality Sensitive Orderings in Doubling Metrics
by: La, An, et al.
Published: (2024)

Tight Bounds on the Number of Closest Pairs in Vertical Slabs
by: Biniaz, Ahmad, et al.
Published: (2025)

Contraction Clustering (RASTER): A Very Fast Big Data Algorithm for Sequential and Parallel Density-Based Clustering in Linear Time, Constant Memory, and a Single Pass
by: Ulm, Gregor, et al.
Published: (2019)

Near-Optimal Bounds for Parameterized Euclidean k-means
by: Cohen-Addad, Vincent, et al.
Published: (2026)

Space Complexity of Euclidean Clustering
by: Zhu, Xiaoyi, et al.
Published: (2024)

Faster Approximation Scheme for Euclidean $k$-TSP
by: van Wijland, Ernest, et al.
Published: (2023)

Euclidean distance compression via deep random features
by: Leroux, Brett, et al.
Published: (2024)

A Lossless Deamortization for Dynamic Greedy Set Cover
by: Solomon, Shay, et al.
Published: (2024)

Computing Diameter +1 in Truly Subquadratic Time for Unit-Disk Graphs
by: Chang, Hsien-Chih, et al.
Published: (2024)

Almost-Optimal Upper and Lower Bounds for Clustering in Low Dimensional Euclidean Spaces
by: Cohen-Addad, Vincent, et al.
Published: (2026)

The Power of Recursive Embeddings for $\ell_p$ Metrics
by: Krauthgamer, Robert, et al.
Published: (2025)

NP-hardness and a PTAS for the Euclidean Steiner Line Problem
by: Bartlmae, Simon, et al.
Published: (2024)

Tight bounds for the learning of homotopy à la Niyogi, Smale, and Weinberger for subsets of Euclidean spaces and of Riemannian manifolds
by: Attali, Dominique, et al.
Published: (2022)

Even Faster $(Δ+ 1)$-Edge Coloring via Shorter Multi-Step Vizing Chains
by: Bhattacharya, Sayan, et al.
Published: (2024)

Parks and Recreation: Color Fault-Tolerant Spanners Made Local
by: Parter, Merav, et al.
Published: (2024)

Charting the Diameter Computation Landscape of Geometric Intersection Graphs in Three Dimensions and Higher
by: Chan, Timothy M., et al.
Published: (2026)