TY - JOUR
T1 - The lion and man game on polyhedral surfaces with obstacles
AU - Noori, Narges
AU - Isler, Volkan I
N1 - Publisher Copyright:
© 2018 Elsevier B.V.
PY - 2018/8/29
Y1 - 2018/8/29
N2 - We study a geometric version of the cops and robbers game known as the lion and man game. In this game, a group of lions (the pursuers) try to capture a man (the evader). The players have equal speed. They can observe each other at all times. While the lion and man game is well-studied in planar domains such as polygons, very little is known about its properties in higher dimensions. In this paper, we study the game when played on the surface of a polyhedron with or without boundary, possibly in the presence of obstacles (i.e. forbidden regions). In particular, in the absence of obstacles, the surface has genus zero, and it can be homeomorphic to either a disk or a sphere. We assume that the input surface is triangulated. We show that three lions with non-zero capture distance δ can capture the man in O(([Formula presented]+[Formula presented]+N)2[Formula presented]+([Formula presented]+[Formula presented]+N)D) steps where A is the area, L is the total edge length of the polyhedron, N is the number of triangular faces used in the representation of the polyhedron, and D is the length of the longest shortest path on the surface.
AB - We study a geometric version of the cops and robbers game known as the lion and man game. In this game, a group of lions (the pursuers) try to capture a man (the evader). The players have equal speed. They can observe each other at all times. While the lion and man game is well-studied in planar domains such as polygons, very little is known about its properties in higher dimensions. In this paper, we study the game when played on the surface of a polyhedron with or without boundary, possibly in the presence of obstacles (i.e. forbidden regions). In particular, in the absence of obstacles, the surface has genus zero, and it can be homeomorphic to either a disk or a sphere. We assume that the input surface is triangulated. We show that three lions with non-zero capture distance δ can capture the man in O(([Formula presented]+[Formula presented]+N)2[Formula presented]+([Formula presented]+[Formula presented]+N)D) steps where A is the area, L is the total edge length of the polyhedron, N is the number of triangular faces used in the representation of the polyhedron, and D is the length of the longest shortest path on the surface.
KW - Lion and man game
KW - Piecewise linear two-dimensional surfaces
KW - Polyhedral surfaces
KW - Pursuit-evasion
UR - http://www.scopus.com/inward/record.url?scp=85046684796&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85046684796&partnerID=8YFLogxK
U2 - 10.1016/j.tcs.2018.04.041
DO - 10.1016/j.tcs.2018.04.041
M3 - Article
AN - SCOPUS:85046684796
SN - 0304-3975
VL - 739
SP - 39
EP - 58
JO - Theoretical Computer Science
JF - Theoretical Computer Science
ER -