An efficient algorithm for the three-guard problem

DOI10.1016/J.DAM.2008.05.007MaRDI QIDQ1003478zbMATH OpenOpenAlexFDO

Authors Xuehou Tan

Publication date 4 March 2009

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2008.05.007

zbMATH Keywords

computational geometryweak visibilityray shootinglink-2-visibilitythree-guard problem

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• AN OPTIMAL ALGORITHM FOR THE TWO-GUARD PROBLEM
• An efficient algorithm for the 3-satisfiability problem
• The guarding problem -- complexity and approximation
• An Efficient Algorithm for Mobile Guarded Guards in Simple Grids
• An approximate algorithm for the three-machine problem
• An efficient algorithm for solving Troesch's problem
• An Optimal Algorithm for the Maximum Three-Chain Problem
• An efficient algorithm for guard placement in polygons with holes
• scientific article; zbMATH DE number 4018246

Cites work

• scientific article; zbMATH DE number 2080272 (Why is no real title available?)
• scientific article; zbMATH DE number 1834577 (Why is no real title available?)
• scientific article; zbMATH DE number 1445396 (Why is no real title available?)
• A unified and efficient solution to the room search problem
• AN OPTIMAL ALGORITHM FOR THE TWO-GUARD PROBLEM
• Algorithms and Computation
• Characterizing LR-visibility polygons and related problems
• Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
• SEARCHING FOR A MOBILE INTRUDER IN A CORRIDOR —THE OPEN EDGE VARIANT OF THE POLYGON SEARCH PROBLEM
• Searching for a Mobile Intruder in a Polygonal Region
• Sweeping simple polygons with the minimum number of chain guards
• THE TWO GUARDS PROBLEM
• Two-Guard Walkability of Simple Polygons
• Visibility and intersection problems in plane geometry

Cited in

(3)

• Minimization of the maximum distance between the two guards patrolling a polygonal region
• Characterizing and recognizing LR-visibility polygons
• Algorithms and Computation

This page was built for publication: An efficient algorithm for the three-guard problem

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