Line-of-sight pursuit in monotone and scallop polygons

DOI10.1142/S0218195919500122MaRDI QIDQ5149564zbMATH OpenOpenAlexFDO

Authors Lindsay Berry, Andrew Beveridge, Volkan Isler, Zachary Keller, Alana Shine, Jun Yi Wang, Jane V. Butterfield

Publication date 11 February 2021

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

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

zbMATH Keywords

monotone polygonpursuit-evasionsweepable polygon

Mathematics Subject Classification ID

Positional games (pursuit and evasion, etc.) (91A24)

Abstract: We study a turn-based game in a simply connected polygonal environment $Q$ between a pursuer $P$ and an adversarial evader $E$. Both players can move in a straight line to any point within unit distance during their turn. The pursuer $P$ wins by capturing the evader, meaning that their distance satisfies $d(P,E)leq1$, while the evader wins by eluding capture forever. Both players have a map of the environment, but they have different sensing capabilities. The evader $E$ always knows the location of $P$. Meanwhile, $P$ only has line-of-sight visibility: $P$ observes the evader's position only when the line segment connecting them lies entirely within the polygon. Therefore $P$ must search for $E$ when the evader is hidden from view. We provide a winning strategy for $P$ in two families of polygons: monotone polygons and scallop polygons. In both families, a straight line $L$ can be moved continuously over $Q$ so that (1) $LcapQ$ is a line segment and (2) every point on the boundary $partialQ$ is swept exactly once. These are both subfamilies of strictly sweepable polygons. The sweeping motion for a monotone polygon is a single translation, and the sweeping motion for a scallop polygon is a single rotation. Our algorithms use rook's strategy during its pursuit phase, rather than the well-known lion's strategy. The rook's strategy is crucial for obtaining a capture time that is linear in the area of $Q$. For both monotone and scallop polygons, our algorithm has a capture time of $O(n(Q)+mboxarea(Q))$, where $n(Q)$ is the number of polygon vertices.

Recommendations

• A leapfrog strategy for pursuit-evasion in a polygonal environment
• Visibility-based pursuit-evasion in a polygonal environment
• Capture bounds for visibility-based pursuit evasion
• Capture bounds for visibility-based pursuit evasion
• scientific article; zbMATH DE number 1754612

Cites work

• A framework for pursuit evasion games in
• A game of cops and robbers
• An Optimal Algorithm for Finding the Kernel of a Polygon
• Capture bounds for visibility-based pursuit evasion
• Capture pursuit games on unbounded domains
• GENERALIZING MONOTONICITY: ON RECOGNIZING SPECIAL CLASSES OF POLYGONS AND POLYHEDRA
• scientific article; zbMATH DE number 3972833 (Why is no real title available?)
• scientific article; zbMATH DE number 3659884 (Why is no real title available?)
• scientific article; zbMATH DE number 3590298 (Why is no real title available?)
• Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
• On geodesic properties of polygons relevant to linear time triangulation
• Pursuit-evasion in a two-dimensional domain
• Recognizing polygons, or how to spy
• Solution of David Gale's lion and man problem
• The game of cops and robbers on graphs
• The lion and man game on polyhedral surfaces with obstacles
• THE TWO GUARDS PROBLEM
• Two-Guard Walkability of Simple Polygons
• Vertex-to-vertex pursuit in a graph
• Visibility-based pursuit-evasion with bounded speed

Cited in

(1)

• A leapfrog strategy for pursuit-evasion in a polygonal environment

This page was built for publication: Line-of-sight pursuit in monotone and scallop polygons

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