Buchumschlag

The Contiguous Art Gallery Problem is in Θ(n log n)

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	de Berg, Sarita, Conradi, Jacobus, van der Hoog, Ivor, Rotenberg, Eva
Format:	Preprint
Veröffentlicht:	2025
Schlagworte:	Computational Geometry Data Structures and Algorithms
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

On computing the (exact) Fréchet distance with a frog
von: Conradi, Jacobus, et al.
Veröffentlicht: (2025)

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

Simpler and Faster Contiguous Art Gallery
von: de Berg, Sarita, et al.
Veröffentlicht: (2025)

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

Tight Universal Bounds for Partially Presorted Pareto Front and Convex Hull
von: van der Hoog, Ivor, et al.
Veröffentlicht: (2025)

Engineering Fully Dynamic Convex Hulls
von: van der Hoog, Ivor, et al.
Veröffentlicht: (2026)

Data Structures for Approximate Discrete Fréchet Distance
von: van der Hoog, Ivor, et al.
Veröffentlicht: (2022)

Instance and Universally Optimal Bounds for Imprecise Pareto Fronts
von: de Berg, Sarita, et al.
Veröffentlicht: (2026)

Efficient Greedy Discrete Subtrajectory Clustering
von: van der Hoog, Ivor, et al.
Veröffentlicht: (2025)

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

Simpler Universally Optimal Dijkstra
von: van der Hoog, Ivor, et al.
Veröffentlicht: (2025)

Simpler Optimal Sorting from a Directed Acyclic Graph
von: van der Hoog, Ivor, et al.
Veröffentlicht: (2024)

The Presort Hierarchy for Geometric Problems
von: van der Hoog, Ivor, et al.
Veröffentlicht: (2026)

Dynamic Indexing Through Learned Indices with Worst-case Guarantees
von: Gæde, Emil Toftegaard, et al.
Veröffentlicht: (2025)

Local Density and its Distributed Approximation
von: Christiansen, Aleksander Bjørn, et al.
Veröffentlicht: (2024)

Near-Optimal Heaps and Dijkstra on Pointer Machines
von: van der Hoog, Ivor, et al.
Veröffentlicht: (2026)

Local Routing on Ordered $Θ$-graphs
von: van Renssen, André, et al.
Veröffentlicht: (2025)

The Complexity of Geodesic Spanners
von: de Berg, Sarita, et al.
Veröffentlicht: (2023)

A Practical Algorithm with Performance Guarantees for the Art Gallery Problem
von: Hengeveld, Simon, et al.
Veröffentlicht: (2020)

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

An $O(n \log n)$-Time Approximation Scheme for Geometric Many-to-Many Matching
von: Bandyapadhyay, Sayan, et al.
Veröffentlicht: (2024)

From Theory to Practice: Engineering Approximation Algorithms for Dynamic Orientation
von: Großmann, Ernestine, et al.
Veröffentlicht: (2025)

Tight Bounds for Sorting Under Partial Information
von: van der Hoog, Ivor, et al.
Veröffentlicht: (2024)

The Complexity of Geodesic Spanners using Steiner Points
von: de Berg, Sarita, et al.
Veröffentlicht: (2024)

A Deterministic Bicriteria Approximation Algorithm for the Art Gallery Problem
von: Elbassioni, Khaled
Veröffentlicht: (2025)

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

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

Lower Bounds for Dominating Set in Ball Graphs and for Weighted Dominating Set in Unit-Ball Graphs
von: de Berg, Mark, et al.
Veröffentlicht: (2026)

The Complexity of Dynamic LZ77 is $\tildeΘ(n^{2/3})$
von: Boneh, Itai, et al.
Veröffentlicht: (2025)

Dominance for Containment Problems
von: Akram, Waseem, et al.
Veröffentlicht: (2022)

Range Counting Oracles for Geometric Problems
von: Driemel, Anne, et al.
Veröffentlicht: (2025)

Algorithms for Halfplane Coverage and Related Problems
von: Wang, Haitao, et al.
Veröffentlicht: (2024)

On the Complexity of the Ordered Covering Problem in Distance Geometry
von: Souza, Michael, et al.
Veröffentlicht: (2025)

On Approximating the Weighted Region Problem in Square Tessellations
von: Kakimura, Naonori, et al.
Veröffentlicht: (2024)

Improved Algorithms for Distance Selection and Related Problems
von: Wang, Haitao, et al.
Veröffentlicht: (2023)

On the Line-Separable Unit-Disk Coverage and Related Problems
von: Liu, Gang, et al.
Veröffentlicht: (2023)

Single-Source Shortest Path Problem in Weighted Disk Graphs
von: An, Shinwoo, et al.
Veröffentlicht: (2025)

Robust Algorithms for Path and Cycle Problems in Geometric Intersection Graphs
von: Marin, Malory, et al.
Veröffentlicht: (2025)

NP-hardness and a PTAS for the Euclidean Steiner Line Problem
von: Bartlmae, Simon, et al.
Veröffentlicht: (2024)

On Line-Separable Weighted Unit-Disk Coverage and Related Problems
von: Liu, Gang, et al.
Veröffentlicht: (2024)