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.ISAAC.2022.67
URN: urn:nbn:de:0030-drops-173522
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/17352/
Go to the corresponding LIPIcs Volume Portal

Rieck, Christian ; Scheffer, Christian

The Dispersive Art Gallery Problem

pdf-format:
LIPIcs-ISAAC-2022-67.pdf (1 MB)

Abstract

We introduce a new variant of the art gallery problem that comes from safety issues. In this variant we are not interested in guard sets of smallest cardinality, but in guard sets with largest possible distances between these guards. To the best of our knowledge, this variant has not been considered before. We call it the Dispersive Art Gallery Problem. In particular, in the dispersive art gallery problem we are given a polygon ? and a real number ?, and want to decide whether ? has a guard set such that every pair of guards in this set is at least a distance of ? apart.
In this paper, we study the vertex guard variant of this problem for the class of polyominoes. We consider rectangular visibility and distances as geodesics in the L₁-metric. Our results are as follows. We give a (simple) thin polyomino such that every guard set has minimum pairwise distances of at most 3. On the positive side, we describe an algorithm that computes guard sets for simple polyominoes that match this upper bound, i.e., the algorithm constructs worst-case optimal solutions. We also study the computational complexity of computing guard sets that maximize the smallest distance between all pairs of guards within the guard sets. We prove that deciding whether there exists a guard set realizing a minimum pairwise distance for all pairs of guards of at least 5 in a given polyomino is NP-complete.
We were also able to find an optimal dynamic programming approach that computes a guard set that maximizes the minimum pairwise distance between guards in tree-shaped polyominoes, i.e., computes optimal solutions; due to space constraints, details can be found in the full version of our paper [Christian Rieck and Christian Scheffer, 2022]. Because the shapes constructed in the NP-hardness reduction are thin as well (but have holes), this result completes the case for thin polyominoes.

BibTeX - Entry

@InProceedings{rieck_et_al:LIPIcs.ISAAC.2022.67,
  author =	{Rieck, Christian and Scheffer, Christian},
  title =	{{The Dispersive Art Gallery Problem}},
  booktitle =	{33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
  pages =	{67:1--67:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-258-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{248},
  editor =	{Bae, Sang Won and Park, Heejin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/17352},
  URN =		{urn:nbn:de:0030-drops-173522},
  doi =		{10.4230/LIPIcs.ISAAC.2022.67},
  annote =	{Keywords: Art gallery, dispersion, polyominoes, NP-completeness, r-visibility, vertex guards, L₁-metric, worst-case optimal}
}

Keywords: Art gallery, dispersion, polyominoes, NP-completeness, r-visibility, vertex guards, L₁-metric, worst-case optimal
Collection: 33rd International Symposium on Algorithms and Computation (ISAAC 2022)
Issue Date: 2022
Date of publication: 14.12.2022

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