AN OPTIMAL ALGORITHM FOR THE TWO-GUARD PROBLEM

DOI10.1142/S0218195996000034zbMath0851.68108OpenAlexW2159148319MaRDI QIDQ4880208

Paul J. Heffernan

Publication date: 4 June 1996

Published in: International Journal of Computational Geometry & Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s0218195996000034

zbMATH Keywords

shortest pathstwo-guard problemshortest path treescounter walk problem

Mathematics Subject Classification ID

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

Related Items (17)

Sweeping simple polygons with the minimum number of chain guards ⋮ A linear-time 2-approximation algorithm for the watchman route problem for simple polygons ⋮ AN ALGORITHM FOR SEARCHING A POLYGONAL REGION WITH A FLASHLIGHT ⋮ SEARCHING A ROOM BY TWO GUARDS ⋮ A Linear-Time Algorithm for Finding All Door Locations That Make a Room Searchable ⋮ Searching for mobile intruders in circular corridors by two 1-searchers ⋮ Optimum sweeps of simple polygons with two guards ⋮ Minimization of the maximum distance between the two guards patrolling a polygonal region ⋮ Characterizing and recognizing LR-visibility polygons ⋮ FINDING ALL DOOR LOCATIONS THAT MAKE A ROOM SEARCHABLE ⋮ A unified and efficient solution to the room search problem ⋮ SEARCHING A POLYGONAL REGION FROM THE BOUNDARY ⋮ SEARCHING A POLYGONAL ROOM WITH ONE DOOR BY A 1-SEARCHER ⋮ ON HAMILTONIAN TRIANGULATIONS IN SIMPLE POLYGONS ⋮ An efficient algorithm for the three-guard problem ⋮ CLEARING A POLYGON WITH TWO 1-SEARCHERS ⋮ EDGE GUARDS IN STRAIGHT WALKABLE POLYGONS

This page was built for publication: AN OPTIMAL ALGORITHM FOR THE TWO-GUARD PROBLEM