License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2018.60
URN: urn:nbn:de:0030-drops-100089
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/10008/
Go to the corresponding LIPIcs Volume Portal

Aurenhammer, Franz ; Steinkogler, Michael ; Klein, Rolf

Partially Walking a Polygon

pdf-format:
LIPIcs-ISAAC-2018-60.pdf (0.3 MB)

Abstract

Deciding two-guard walkability of an n-sided polygon is a well-understood problem. We study the following more general question: How far can two guards reach from a given source vertex while staying mutually visible, in the (more realistic) case that the polygon is not entirely walkable? There can be Theta(n) such maximal walks, and we show how to find all of them in O(n log n) time.

BibTeX - Entry

@InProceedings{aurenhammer_et_al:LIPIcs:2018:10008,
  author =	{Franz Aurenhammer and Michael Steinkogler and Rolf Klein},
  title =	{{Partially Walking a Polygon}},
  booktitle =	{29th International Symposium on Algorithms and Computation  (ISAAC 2018)},
  pages =	{60:1--60:9},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{123},
  editor =	{Wen-Lian Hsu and Der-Tsai Lee and Chung-Shou Liao},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/10008},
  URN =		{urn:nbn:de:0030-drops-100089},
  doi =		{10.4230/LIPIcs.ISAAC.2018.60},
  annote =	{Keywords: Polygon, guard walk, visibility}
}

Keywords: Polygon, guard walk, visibility
Collection: 29th International Symposium on Algorithms and Computation (ISAAC 2018)
Issue Date: 2018
Date of publication: 06.12.2018

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