1 Search Results for "Hengeveld, Simon B."

Document

DOI: 10.4230/LIPIcs.SoCG.2021.44

A Practical Algorithm with Performance Guarantees for the Art Gallery Problem

Authors: Simon B. Hengeveld and Tillmann Miltzow

Published in: LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021)

Abstract

Given a closed simple polygon P, we say two points p,q see each other if the segment seg(p,q) is fully contained in P. The art gallery problem seeks a minimum size set G ⊂ P of guards that sees P completely. The only currently correct algorithm to solve the art gallery problem exactly uses algebraic methods. As the art gallery problem is ∃ ℝ-complete, it seems unlikely to avoid algebraic methods, for any exact algorithm, without additional assumptions. In this paper, we introduce the notion of vision-stability. In order to describe vision-stability consider an enhanced guard that can see "around the corner" by an angle of δ or a diminished guard whose vision is by an angle of δ "blocked" by reflex vertices. A polygon P has vision-stability δ if the optimal number of enhanced guards to guard P is the same as the optimal number of diminished guards to guard P. We will argue that most relevant polygons are vision-stable. We describe a one-shot vision-stable algorithm that computes an optimal guard set for vision-stable polygons using polynomial time and solving one integer program. It guarantees to find the optimal solution for every vision-stable polygon. We implemented an iterative vision-stable algorithm and show its practical performance is slower, but comparable with other state-of-the-art algorithms. The practical implementation can be found at: https://github.com/simonheng/AGPIterative. Our iterative algorithm is inspired and follows closely the one-shot algorithm. It delays several steps and only computes them when deemed necessary. Given a chord c of a polygon, we denote by n(c) the number of vertices visible from c. The chord-visibility width (cw(P)) of a polygon is the maximum n(c) over all possible chords c. The set of vision-stable polygons admit an FPT algorithm when parameterized by the chord-visibility width. Furthermore, the one-shot algorithm runs in FPT time when parameterized by the number of reflex vertices.

Cite as

Simon B. Hengeveld and Tillmann Miltzow. A Practical Algorithm with Performance Guarantees for the Art Gallery Problem. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 44:1-44:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{hengeveld_et_al:LIPIcs.SoCG.2021.44,
  author =	{Hengeveld, Simon B. and Miltzow, Tillmann},
  title =	{{A Practical Algorithm with Performance Guarantees for the Art Gallery Problem}},
  booktitle =	{37th International Symposium on Computational Geometry (SoCG 2021)},
  pages =	{44:1--44:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-184-9},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{189},
  editor =	{Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.44},
  URN =		{urn:nbn:de:0030-drops-138433},
  doi =		{10.4230/LIPIcs.SoCG.2021.44},
  annote =	{Keywords: Art Gallery, Parametrized complexity, Integer Programming, Visibility}
}

Refine by Author
1 Hengeveld, Simon B.
1 Miltzow, Tillmann

Refine by Classification
1 Theory of computation → Computational geometry

Refine by Keyword
1 Art Gallery
1 Integer Programming
1 Parametrized complexity
1 Visibility

Refine by Type
1 document

Refine by Publication Year
1 2021

1 Search Results for "Hengeveld, Simon B."

A Practical Algorithm with Performance Guarantees for the Art Gallery Problem

Abstract

Cite as

Thanks for your feedback!

Could not send message