Imagen de Portada

A dynamic $(1+\varepsilon)$-spanner for disk intersection graphs

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	de Berg, Sarita, van der Hoog, Ivor, Rotenberg, Eva, Vistisen, Johanne M., Wong, Sampson
Formato:	Preprint
Publicado:	2026
Materias:	Computational Geometry Data Structures and Algorithms
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

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

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

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

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

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

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

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

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

Simpler Optimal Sorting from a Directed Acyclic Graph
por: van der Hoog, Ivor, et al.
Publicado: (2024)

Tight Better-Than-Worst-Case Bounds for Element Distinctness and Set Intersection
por: van der Hoog, Ivor, et al.
Publicado: (2025)

Simpler Universally Optimal Dijkstra
por: van der Hoog, Ivor, et al.
Publicado: (2025)

Near-Optimal Heaps and Dijkstra on Pointer Machines
por: van der Hoog, Ivor, et al.
Publicado: (2026)

Dynamic Indexing Through Learned Indices with Worst-case Guarantees
por: Gæde, Emil Toftegaard, et al.
Publicado: (2025)

Local Density and its Distributed Approximation
por: Christiansen, Aleksander Bjørn, et al.
Publicado: (2024)

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

From Theory to Practice: Engineering Approximation Algorithms for Dynamic Orientation
por: Großmann, Ernestine, et al.
Publicado: (2025)

Tight Bounds for Sorting Under Partial Information
por: van der Hoog, Ivor, et al.
Publicado: (2024)

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

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

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

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

Dynamic parameterized problems on unit disk graphs
por: An, Shinwoo, et al.
Publicado: (2024)

Instance-Optimal Imprecise Convex Hull
por: de Berg, Sarita, et al.
Publicado: (2025)

New weighted additive spanners
por: La, An, et al.
Publicado: (2024)

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

Approximating Multiplicatively Weighted Voronoi Diagrams: Efficient Construction with Linear Size
por: Gudmundsson, Joachim, et al.
Publicado: (2021)

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

Approximating Klee's Measure Problem and a Lower Bound for Union Volume Estimation
por: Bringmann, Karl, et al.
Publicado: (2024)

Lower bounds on collective additive spanners
por: Corneil, Derek G., et al.
Publicado: (2025)

Fully dynamic biconnectivity in $\tilde{\mathcal{O}}(\log^2 n)$ time
por: Holm, Jacob, et al.
Publicado: (2025)

Private graph colouring with limited defectiveness
por: Christiansen, Aleksander B. G., et al.
Publicado: (2024)

A face cover perspective to $\ell_1$ embeddings of planar graphs
por: Filtser, Arnold
Publicado: (2019)

Finding maximum matchings in RDV graphs efficiently
por: Biedl, Therese, et al.
Publicado: (2024)

Deterministic $(1+\varepsilon)$-Approximate Maximum Matching with $\mathsf{poly}(1/\varepsilon)$ Passes in the Semi-Streaming Model and Beyond
por: Fischer, Manuela, et al.
Publicado: (2021)

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

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

Sparsity-Parameterised Dynamic Edge Colouring
por: Christiansen, Aleksander B. G., et al.
Publicado: (2023)

Sequential non-determinism in tile self-assembly: a general framework and an application to efficient temperature-1 self-assembly of squares
por: Furcy, David, et al.
Publicado: (2024)

Min-1-Planarity is NP-Hard
por: Okada, Yuto
Publicado: (2026)

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