Buchumschlag

A Practical Algorithm with Performance Guarantees for the Art Gallery Problem

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Hengeveld, Simon, Miltzow, Tillmann
Format:	Preprint
Veröffentlicht:	2020
Schlagworte:	Computational Geometry Discrete Mathematics 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

Framework for $\exists \mathbb{R}$-Completeness of Two-Dimensional Packing Problems
von: Abrahamsen, Mikkel, et al.
Veröffentlicht: (2020)

On Classifying Continuous Constraint Satisfaction Problems
von: Miltzow, Tillmann, et al.
Veröffentlicht: (2021)

Geometric Thickness of Multigraphs is $\exists \mathbb{R}$-complete
von: Förster, Henry, et al.
Veröffentlicht: (2023)

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

Quadratic-Time Algorithm for the Maximum-Weight $(k, \ell)$-Sparse Subgraph Problem
von: Deák, Bence, et al.
Veröffentlicht: (2025)

Reweighted Spectral Partitioning Works: A Simple Algorithm for Vertex Separators in Special Graph Classes
von: Spalding-Jamieson, Jack
Veröffentlicht: (2025)

Algorithms for Euclidean Distance Matrix Completion: Exploiting Proximity to Triviality
von: Fomin, Fedor V., et al.
Veröffentlicht: (2026)

Boosting Rectilinear Steiner Minimum Tree Algorithms with Augmented Bounding Volume Hierarchy
von: Yang, Puhan, et al.
Veröffentlicht: (2025)

A Polynomial Coreset for Furthest Neighbor in Planar Metrics
von: Kluk, Kacper, et al.
Veröffentlicht: (2026)

Efficient Algorithms and Implementations for Extracting Maximum-Size $(k,\ell)$-Sparse Subgraphs
von: Madarasi, Péter
Veröffentlicht: (2025)

Slant/Gokigen Naname is NP-complete, and Some Variations are in P
von: Lynch, Jayson, et al.
Veröffentlicht: (2025)

Internally-Convex Drawings of Outerplanar Graphs in Small Area
von: Bekos, Michael A., et al.
Veröffentlicht: (2025)

When Distances Lie: Euclidean Embeddings in the Presence of Outliers and Distance Violations
von: Bentert, Matthias, et al.
Veröffentlicht: (2025)

Simple Compact Monotone Tree Drawings
von: Oikonomou, Anargyros, et al.
Veröffentlicht: (2017)

Upward Pointset Embeddings of Planar st-Graphs
von: Alegria, Carlos, et al.
Veröffentlicht: (2024)

From Tutte to Floater and Gotsman: On the Resolution of Planar Straight-line Drawings and Morphs
von: Di Battista, Giuseppe, et al.
Veröffentlicht: (2021)

Distance Approximating Minors for Planar and Minor-Free Graphs
von: Chang, Hsien-Chih, et al.
Veröffentlicht: (2025)

Freeze-Tag in $L_1$ has Wake-up Time Five
von: Bonichon, Nicolas, et al.
Veröffentlicht: (2024)

An algorithm for accurate and simple-looking metaphorical maps
von: Katsanou, Eleni, et al.
Veröffentlicht: (2025)

On Tight Robust Coresets for $k$-Medians Clustering
von: Huang, Lingxiao, et al.
Veröffentlicht: (2025)

The Squishy Grid Problem
von: Cai, Zixi, et al.
Veröffentlicht: (2025)

Beyond Bits: An Introduction to Computation over the Reals
von: Miltzow, Tillmann
Veröffentlicht: (2026)

A New and Faster Representation for Counting Integer Points in Parametric Polyhedra
von: Gribanov, D., et al.
Veröffentlicht: (2023)

Hyperplanes Avoiding Problem and Integer Points Counting in Polyhedra
von: Dakhno, Grigorii, et al.
Veröffentlicht: (2024)

Implicit representations via the polynomial method
von: Cardinal, Jean, et al.
Veröffentlicht: (2026)

A Nearly Optimal Deterministic Algorithm for Online Transportation Problem
von: Harada, Tsubasa, et al.
Veröffentlicht: (2024)

Parameterized Algorithms for Balanced Cluster Edge Modification Problems
von: Madathil, Jayakrishnan, et al.
Veröffentlicht: (2024)

Algorithmic Results for Weak Roman Domination Problem in Graphs
von: Paul, Kaustav, et al.
Veröffentlicht: (2024)

Approximation Algorithm of Minimum All-Ones Problem for Arbitrary Graphs
von: Wang, Chen, et al.
Veröffentlicht: (2024)

Greediness is not always a vice: Efficient Discovery Algorithms for Assignment Problems
von: Duvignau, Romaric, et al.
Veröffentlicht: (2024)

Permutation Match Puzzles: How Young Tanvi Learned About Computational Complexity
von: Gajjar, Kshitij, et al.
Veröffentlicht: (2026)

Graph Coloring Below Guarantees via Co-Triangle Packing
von: Akmal, Shyan, et al.
Veröffentlicht: (2025)

O(1)-Distortion Planar Emulators for String Graphs
von: Chang, Hsien-Chih, et al.
Veröffentlicht: (2025)

Improved Guarantees for Offline Stochastic Matching via New Ordered Contention Resolution Schemes
von: Brubach, Brian, et al.
Veröffentlicht: (2021)

A Fixed-Parameter Algorithm for the Kneser Problem
von: Haviv, Ishay
Veröffentlicht: (2022)

Quasi-Monte Carlo Beyond Hardy-Krause
von: Bansal, Nikhil, et al.
Veröffentlicht: (2024)

Space Efficient Algorithms for Parameterised Problems
von: Akhtar, Sheikh Shakil, et al.
Veröffentlicht: (2025)

Algorithmic Aspects of Temporal Betweenness
von: Buß, Sebastian, et al.
Veröffentlicht: (2020)

Approximation Algorithms for Optimal Hopsets
von: Dinitz, Michael, et al.
Veröffentlicht: (2025)

Flip Distance of Triangulations of Convex Polygons / Rotation Distance of Binary Trees is NP-complete
von: Dorfer, Joseph
Veröffentlicht: (2026)