Mobile versus point guards

DOI10.1007/S00454-018-9996-XMaRDI QIDQ1716007zbMATH OpenOpenAlexWikidataFDO

Authors Tamás Róbert Mezei, Ervin Győri

Publication date 29 January 2019

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1706.02619

zbMATH Keywords

orthogonal polygonmobile guardart gallery problemsliding cameras

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Packing and covering in (2) dimensions (aspects of discrete geometry) (52C15)

Abstract: We study the problem of guarding orthogonal art galleries with horizontal mobile guards (alternatively, vertical) and point guards, using "rectangular vision". We prove a sharp bound on the minimum number of point guards required to cover the gallery in terms of the minimum number of vertical mobile guards and the minimum number of horizontal mobile guards required to cover the gallery. Furthermore, we show that the latter two numbers can be calculated in linear time.

Recommendations

• Art gallery theorems for guarded guards.
• scientific article; zbMATH DE number 177851
• Guards, Galleries, Fortresses, and the Octoplex
• Guarding rectangular art galleries
• scientific article; zbMATH DE number 219237

Cites work

• scientific article; zbMATH DE number 4065813 (Why is no real title available?)
• A Short Proof of the Rectilinear Art Gallery Theorem
• A linear-time algorithm for a special case of disjoint set union
• Cooperative mobile guards in grids
• Domination in convex and chordal bipartite graphs
• Generalized guarding and partitioning for rectilinear polygons
• Graph theory
• Guarding orthogonal art galleries using sliding cameras: algorithmic and hardness results
• Guarding orthogonal art galleries with sliding cameras
• Linear-time 3-approximation algorithm for the \(r\)-star covering problem
• On \(r\)-guarding thin orthogonal polygons
• On guarding orthogonal polygons with sliding cameras
• POLYGON DECOMPOSITION AND THE ORTHOGONAL ART GALLERY PROBLEM
• Partitioning orthogonal polygons into \(\leq 8\)-vertex pieces, with application to an art gallery theorem
• Perfect Elimination and Chordal Bipartite Graphs
• The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs
• Traditional Galleries Require Fewer Watchmen
• Two NP‐Hard Art‐Gallery Problems for Ortho‐Polygons

Cited in

(2)

• An Efficient Algorithm for Mobile Guarded Guards in Simple Grids
• Guarding in a simple polygon

This page was built for publication: Mobile versus point guards

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