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.SWAT.2018.6
URN: urn:nbn:de:0030-drops-88322
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8832/
Go to the corresponding LIPIcs Volume Portal

Ahn, Hee-Kap ; Oh, Eunjin ; Schlipf, Lena ; Stehn, Fabian ; Strash, Darren

On Romeo and Juliet Problems: Minimizing Distance-to-Sight

pdf-format:
LIPIcs-SWAT-2018-6.pdf (0.7 MB)

Abstract

We introduce a variant of the watchman route problem, which we call the quickest pair-visibility problem. Given two persons standing at points s and t in a simple polygon P with no holes, we want to minimize the distance these persons travel in order to see each other in P. We solve two variants of this problem, one minimizing the longer distance the two persons travel (min-max) and one minimizing the total travel distance (min-sum), optimally in linear time. We also consider a query version of this problem for the min-max variant. We can preprocess a simple n-gon in linear time so that the minimum of the longer distance the two persons travel can be computed in O(log^2 n) time for any two query positions where the two persons lie.

BibTeX - Entry

@InProceedings{ahn_et_al:LIPIcs:2018:8832,
  author =	{Hee-Kap Ahn and Eunjin Oh and Lena Schlipf and Fabian Stehn and Darren Strash},
  title =	{{On Romeo and Juliet Problems: Minimizing Distance-to-Sight}},
  booktitle =	{16th Scandinavian Symposium and Workshops on Algorithm  Theory (SWAT 2018)},
  pages =	{6:1--6:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-068-2},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{101},
  editor =	{David Eppstein},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8832},
  URN =		{urn:nbn:de:0030-drops-88322},
  doi =		{10.4230/LIPIcs.SWAT.2018.6},
  annote =	{Keywords: Visibility polygon, shortest-path, watchman problems}
}

Keywords: Visibility polygon, shortest-path, watchman problems
Collection: 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)
Issue Date: 2018
Date of publication: 04.06.2018

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