Pursuit evasion on polyhedral surfaces

DOI10.1007/S00453-015-9988-7MaRDI QIDQ5963379zbMATH OpenOpenAlexFDO

Authors Kyle Klein, Subhash Suri

Publication date 19 February 2016

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.696.3702

zbMATH Keywords

cops and robberslion and man gamepolyhedral surfacepursuit-evasion

Mathematics Subject Classification ID

Polyhedral manifolds (52B70) Positional games (pursuit and evasion, etc.) (91A24) Games involving graphs (91A43) Combinatorial games (91A46) Discrete-time games (91A50)

Review text

The authors consider a discrete-time pursuit-evasion game played on the surface of a 3-dimensional polyhedron. Play alternates between a team of pursuers and a single evader. On the pursuers' turn, all pursuers may simultaneously move a distance of up to 1 on the surface; on the evader's turn, they may likewise move up to 1 unit away from their current location. The pursuers win if some pursuer has the same location as the evader at the end of a pursuer turn, while the evader wins by evading capture indefinitely. All players are aware of each others' locations at all times. The main question the authors are interested in is the number of pursuers required to guarantee that the pursuers win. The authors show that on some genus-0 surfaces, at least \(3\) pursuers may be required, and present a surface for which this is the case. They also show that \(4\) pursuers can catch the evader on any genus-\(0\) surface and, more generally, that \(4g+4\) pursuers can catch the evader on a surface of genus \(g\). They also give upper bounds on the number of moves required for the pursuers to achieve victory.

Recommendations

• Pursuit evasion on polyhedral surfaces
• The lion and man game on polyhedral surfaces with obstacles
• Capture bounds for visibility-based pursuit evasion
• Capture bounds for visibility-based pursuit evasion
• The pursuit-evasion game on the 1-skeleton graph of the regular polyhedron. I

Cites work

• A cooperative homicidal Chauffeur game
• A game of cops and robbers
• An ε — Approximation algorithm for weighted shortest paths on polyhedral surfaces
• Capture pursuit games on unbounded domains
• Geometry of Pursuit-Evasion Games on Two-Dimensional Manifolds
• Greedy optimal homotopy and homology generators
• scientific article; zbMATH DE number 1665333 (Why is no real title available?)
• scientific article; zbMATH DE number 3972833 (Why is no real title available?)
• scientific article; zbMATH DE number 1023191 (Why is no real title available?)
• Pursuit evasion on polyhedral surfaces
• Randomized Pursuit-Evasion with Local Visibility
• Searching for a Mobile Intruder in a Polygonal Region
• Solution of David Gale's lion and man problem
• The Discrete Geodesic Problem
• The weighted region problem
• The “Princess and Monster” Game on an Interval

Cited in

(12)

• A short note about pursuit games played on a graph with a given genus
• The lion and man game on polyhedral surfaces with obstacles
• Construction of barrier surfaces in a pursuit-evasion game problem
• The pursuit-evasion game on the 1-skeleton graph of the regular polyhedron. I
• Pursuit evasion on polyhedral surfaces
• Hunter, Cauchy rabbit, and optimal Kakeya sets
• A leapfrog strategy for pursuit-evasion in a polygonal environment
• Pursuit-evasion in a two-dimensional domain
• Smarter Lions: efficient cooperative pursuit in general bounded arenas
• scientific article; zbMATH DE number 7650934 (Why is no real title available?)
• Geometry of pursuit-evasion on second order rotation surfaces
• The game of cops and robber on geodesic spaces

This page was built for publication: Pursuit evasion on polyhedral surfaces

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