A practical algorithm with performance guarantees for the art gallery problem

Cites Work

Title not available (Why is that?)
Title not available (Why is that?)
Title not available (Why is that?)
Title not available (Why is that?)
1.5D terrain guarding problem parameterized by guard range
Recognition and complexity of point visibility graphs
Fixed points, Nash equilibria, and the existential theory of the reals
A nearly optimal algorithm for covering the interior of an art gallery
Guarding galleries and terrains
Covering orthogonal polygons with star polygons: The perfect graph approach
A nearly optimal sensor placement algorithm for boundary coverage
Approximation algorithms for art gallery problems in polygons
Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
Some provably hard crossing number problems
Integer realizations of disk and segment graphs
Efficient guarding of polygons and terrains
An \(O(\lg \lg {\mathrm {OPT}})\)-approximation algorithm for multi-guarding galleries
A fixed-parameter algorithm for guarding 1.5D terrains
Realizability of Graphs and Linkages
LOCATING GUARDS FOR VISIBILITY COVERAGE OF POLYGONS
Who Needs Crossings? Hardness of Plane Graph Rigidity
ETR-Completeness for Decision Versions of Multi-player (Symmetric) Nash Equilibria
Complexity of Some Geometric and Topological Problems
Computational complexity of art gallery problems
Irrational Guards are Sometimes Needed
Intersection Graphs of Rays and Grounded Segments
Two NP‐Hard Art‐Gallery Problems for Ortho‐Polygons
Realization spaces of 4-polytopes are universal
An exact algorithm for minimizing vertex guards on art galleries
Parameterized Analysis of Art Gallery and Terrain Guarding
Smoothing the Gap Between NP and ER
Algorithm 966
The Complexity of Positive Semidefinite Matrix Factorization
Sphere and dot product representations of graphs
Exact solutions and bounds for general art gallery problems
GUARDING ART GALLERIES BY GUARDING WITNESSES
Parameterized Hardness of Art Gallery Problems
Inapproximability results for guarding polygons and terrains
The Parameterized Complexity of Guarding Almost Convex Polygons.
The complexity of the Hausdorff distance
Planar graphs and face areas. Area-universality

This page was built for publication: A practical algorithm with performance guarantees for the art gallery problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6599806)