License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SAND.2022.21
URN: urn:nbn:de:0030-drops-159636
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/15963/
Go to the corresponding LIPIcs Volume Portal

Augustine, John ; Ramachandran, Srikkanth

Brief Announcement: Cooperative Guarding in Polygons with Holes

pdf-format:
LIPIcs-SAND-2022-21.pdf (0.5 MB)

Abstract

We study the Cooperative Guarding problem for polygons with holes in a mobile multi-agents setting. Given a set of agents, initially deployed at a point in a polygon with n vertices and h holes, we require the agents to collaboratively explore and position themselves in such a way that every point in the polygon is visible to at least one agent and that the set of agents are visibly connected. We study the problem under two models of computation, one in which the agents can compute exact distances and angles between two points in its visibility, and one in which agents can only compare distances and angles. In the stronger model, we provide a deterministic O(n) round algorithm to compute such a cooperative guard set while not requiring more than (n + h)/2 agents and O(log n) bits of persistent memory per agent. In the weaker model, we provide an O(n⁴) round algorithm, that does not require more than (n+2h)/2 agents.

BibTeX - Entry

@InProceedings{augustine_et_al:LIPIcs.SAND.2022.21,
  author =	{Augustine, John and Ramachandran, Srikkanth},
  title =	{{Brief Announcement: Cooperative Guarding in Polygons with Holes}},
  booktitle =	{1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)},
  pages =	{21:1--21:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-224-2},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{221},
  editor =	{Aspnes, James and Michail, Othon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/15963},
  URN =		{urn:nbn:de:0030-drops-159636},
  doi =		{10.4230/LIPIcs.SAND.2022.21},
  annote =	{Keywords: Mobile Agents, Art Gallery Problem, Cooperative Guarding}
}

Keywords: Mobile Agents, Art Gallery Problem, Cooperative Guarding
Collection: 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)
Issue Date: 2022
Date of publication: 29.04.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI