A short proof of Chvatal's Watchman Theorem

DOI10.1016/0095-8956(78)90059-XzbMath0376.05018WikidataQ55878068 ScholiaQ55878068MaRDI QIDQ1245840

Steve Fisk

Publication date: 1978

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Mathematics Subject Classification ID

Combinatorial aspects of packing and covering (05B40)

Related Items (90)

Tight bounds for conflict-free chromatic guarding of orthogonal art galleries ⋮ Monitoring maximal outerplanar graphs ⋮ Parameterized Analysis of Art Gallery and Terrain Guarding ⋮ On gallery watchmen in grids ⋮ Bichromatic quadrangulations with Steiner points ⋮ Approximate guarding of monotone and rectilinear polygons ⋮ An efficient algorithm for guard placement in polygons with holes ⋮ Multi-agent deployment for visibility coverage in polygonal environments with holes ⋮ Universal Guard Problems ⋮ Two-floodlight illumination of convex polygons ⋮ Quadrangulations of planar sets ⋮ Line segment visibility with sidedness constraints ⋮ Guarding polyominoes, polycubes and polyhypercubes ⋮ Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons ⋮ Smoothing the Gap Between NP and ER ⋮ Vertex Guarding for Dynamic Orthogonal Art Galleries ⋮ Algorithms for art gallery illumination ⋮ Hiding people in polygons ⋮ Converting triangulations to quadrangulations ⋮ Polychromatic 4-coloring of cubic even embeddings on the projective plane ⋮ Generating even triangulations on the Klein bottle ⋮ Note on an art gallery problem ⋮ Guarding a Polygon Without Losing Touch ⋮ Injectively \(k\)-colored rooted forests ⋮ The visible-volume function of a set of cameras is continuous, piecewise rational, locally Lipschitz, and semi-algebraic in all dimensions ⋮ The dispersive art gallery problem ⋮ Polychromatic 4-coloring of cubic bipartite plane graphs ⋮ Partial domination of maximal outerplanar graphs ⋮ Total domination in maximal outerplanar graphs. II. ⋮ Guarding Art Galleries: The Extra Cost for Sculptures Is Linear ⋮ Improved Bounds for Wireless Localization ⋮ Guarding a set of line segments in the plane ⋮ Combinatorics and complexity of guarding polygons with edge and point 2-transmitters ⋮ The parameterized complexity of guarding almost convex polygons ⋮ Topological art in simple galleries ⋮ Worst-case-optimal algorithms for guarding planar graphs and polyhedral surfaces ⋮ Art gallery theorems for guarded guards. ⋮ Extensions of the Art Gallery Theorem ⋮ Finding minimum witness sets in orthogonal polygons ⋮ On the resolution of the sensitivity conjecture ⋮ Simple agents learn to find their way: an introduction on mapping polygons ⋮ Multiple point visibility and related problems ⋮ Guarding curvilinear art galleries with vertex or point guards ⋮ Note on the paper ``K-vertex guarding simple polygons ⋮ Total domination in plane triangulations ⋮ Distance domination, guarding and covering of maximal outerplanar graphs ⋮ Parity-constrained triangulations with Steiner points ⋮ Distance \(k\)-domination, distance \(k\)-guarding, and distance \(k\)-vertex cover of maximal outerplanar graphs ⋮ Improved bounds for guarding plane graphs with edges ⋮ Guarding polyhedral terrains ⋮ The orthogonal art gallery theorem with constrained guards ⋮ Traditional Galleries Require Fewer Watchmen ⋮ Perfect graphs and guarding rectilinear art galleries ⋮ An addition to art galleries with interior walls ⋮ Approximation algorithms for art gallery problems in polygons ⋮ Improved bounds for wireless localization ⋮ Witness (Delaunay) graphs ⋮ Guarding curvilinear art galleries with edge or mobile guards via 2-dominance of triangulation graphs ⋮ A simple proof of the rectilinear art gallery theorem ⋮ Orthogonal art galleries with interior walls ⋮ Polychromatic 4-coloring of guillotine subdivisions ⋮ Facial achromatic number of triangulations on the sphere ⋮ LOCATING GUARDS FOR VISIBILITY COVERAGE OF POLYGONS ⋮ Art galleries with guards of uniform range of vision ⋮ Unnamed Item ⋮ A Zen master, a Zen monk, a Zen mathematician ⋮ New bounds on guarding problems for orthogonal polygons in the plane using vertex guards with halfplane vision ⋮ Quadrangulations of a polygon with spirality ⋮ Facets for art gallery problems ⋮ Domination and outer connected domination in maximal outerplanar graphs ⋮ Uniqueness of Self-Similar Solutions to the Network Flow in a Given Topological Class ⋮ Exploring and Triangulating a Region by a Swarm of Robots ⋮ Optimal art gallery localization is NP-hard ⋮ Twenty years of progress of \(\mathrm{JCDCG}^3\) ⋮ Multiple-guard kernels of simple polygons ⋮ Convex dominating sets in maximal outerplanar graphs ⋮ Extension to 3-Colorable Triangulations ⋮ Isolation number of maximal outerplanar graphs ⋮ Semipaired domination in maximal outerplanar graphs ⋮ An alternative proof of the rectilinear art gallery theorem ⋮ An \(O(\lg \lg {\mathrm {OPT}})\)-approximation algorithm for multi-guarding galleries ⋮ How to Keep an Eye on Small Things ⋮ Improved bounds for guarding plane graphs with edges ⋮ Art gallery problem with guards whose range of vision is \(180^{\circ}\) ⋮ On the number of guard edges of a polygon ⋮ Independent domination in outerplanar graphs ⋮ On partitioning rectilinear polygons into star-shaped polygons ⋮ Triangles and (total) domination in subcubic graphs ⋮ How to guard orthogonal polygons: diagonal graphs and vertex covers ⋮ Approximability of guarding weak visibility polygons

Cites Work

• A combinatorial theorem in plane geometry

This page was built for publication: A short proof of Chvatal's Watchman Theorem