The lion and man game on polyhedral surfaces with obstacles

Narges Noori, Volkan I Isler

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)39-58
Number of pages20
JournalTheoretical Computer Science
StatePublished - Aug 29 2018

Bibliographical note

Publisher Copyright:
© 2018 Elsevier B.V.


  • Lion and man game
  • Piecewise linear two-dimensional surfaces
  • Polyhedral surfaces
  • Pursuit-evasion


Dive into the research topics of 'The lion and man game on polyhedral surfaces with obstacles'. Together they form a unique fingerprint.

Cite this