Cover Image

The Complexity of Geodesic Spanners

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	de Berg, Sarita, van Kreveld, Marc, Staals, Frank
Format:	Preprint
Published:	2023
Subjects:	Computational Geometry Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

Towards Space Efficient Two-Point Shortest Path Queries in a Polygonal Domain
by: de Berg, Sarita, et al.
Published: (2023)

The Contiguous Art Gallery Problem is in Θ(n log n)
by: de Berg, Sarita, et al.
Published: (2025)

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

Spanner for the $0/1/\infty$ weighted region problem
by: Gudmundsson, Joachim, 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)

A dynamic $(1+\varepsilon)$-spanner for disk intersection graphs
by: de Berg, Sarita, et al.
Published: (2026)

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

Range Counting Oracles for Geometric Problems
by: Driemel, Anne, et al.
Published: (2025)

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

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

Visibility Queries in Simple Polygons
by: Bhore, Sujoy, et al.
Published: (2026)

Smallest Enclosing Disk Queries Using Farthest-Point Voronoi Diagrams
by: Buchin, Kevin, et al.
Published: (2026)

Towards Instance-Optimal Euclidean Spanners
by: Le, Hung, et al.
Published: (2024)

Lower Bounds for Dominating Set in Ball Graphs and for Weighted Dominating Set in Unit-Ball Graphs
by: de Berg, Mark, et al.
Published: (2026)

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

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

Polyline Simplification has Cubic Complexity
by: Bringmann, Karl, et al.
Published: (2018)

The Parameterized Complexity of Extending Stack Layouts
by: Depian, Thomas, et al.
Published: (2024)

On the Complexity of the Ordered Covering Problem in Distance Geometry
by: Souza, Michael, et al.
Published: (2025)

New Complexity and Algorithmic Bounds for Minimum Consistent Subsets
by: Banik, Aritra, et al.
Published: (2024)

Revisiting Graph Modification via Disk Scaling: From One Radius to Interval-Based Radii
by: Depian, Thomas, et al.
Published: (2026)

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

Local Routing on Ordered $Θ$-graphs
by: van Renssen, André, et al.
Published: (2025)

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

Tight Universal Bounds for Partially Presorted Pareto Front and Convex Hull
by: van der Hoog, Ivor, et al.
Published: (2025)

On computing the (exact) Fréchet distance with a frog
by: Conradi, Jacobus, et al.
Published: (2025)

Engineering Fully Dynamic Convex Hulls
by: van der Hoog, Ivor, et al.
Published: (2026)

Data Structures for Approximate Discrete Fréchet Distance
by: van der Hoog, Ivor, et al.
Published: (2022)

Near-tight Bounds for Computing the Fréchet Distance in d-Dimensional Grid Graphs and the Implications for λ-low Dense Curves
by: Conradi, Jacobus, et al.
Published: (2026)

Efficient Greedy Discrete Subtrajectory Clustering
by: van der Hoog, Ivor, et al.
Published: (2025)

Computational Complexities of Folding
by: Eppstein, David
Published: (2024)

Retroactive Monotonic Priority Queues via Range Searching
by: Castro, Lucas, et al.
Published: (2025)

Worst-Case and Smoothed Analysis of the Hartigan-Wong Method for k-Means Clustering
by: Manthey, Bodo, et al.
Published: (2023)

Routing-Controlled Spanners
by: Grigorescu, Elena, et al.
Published: (2024)

Single-Source Shortest Paths and Almost Exact Diameter in Pseudodisk Graphs
by: de Berg, Mark, et al.
Published: (2026)

Directed Buy-at-Bulk Spanners
by: Grigorescu, Elena, et al.
Published: (2024)

New Greedy Spanners and Applications
by: Popova, Elizaveta, et al.
Published: (2026)

Subexponential algorithms in geometric graphs via the subquadratic grid minor property: the role of local radius
by: Berthe, Gaétan, et al.
Published: (2023)