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

Oh, Eunjin

Minimizing Distance-to-Sight in Polygonal Domains

pdf-format:
LIPIcs-ISAAC-2018-59.pdf (0.5 MB)

Abstract

In this paper, we consider the quickest pair-visibility problem in polygonal domains. Given two points in a polygonal domain with h holes of total complexity n, we want to minimize the maximum distance that the two points travel in order to see each other in the polygonal domain. We present an O(n log^2 n+h^2 log^4 h)-time algorithm for this problem. We show that this running time is almost optimal unless the 3sum problem can be solved in O(n^{2-epsilon}) time for some epsilon>0.

BibTeX - Entry

@InProceedings{oh:LIPIcs:2018:10007,
  author =	{Eunjin Oh},
  title =	{{Minimizing Distance-to-Sight in Polygonal Domains}},
  booktitle =	{29th International Symposium on Algorithms and Computation  (ISAAC 2018)},
  pages =	{59:1--59:12},
  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/10007},
  URN =		{urn:nbn:de:0030-drops-100073},
  doi =		{10.4230/LIPIcs.ISAAC.2018.59},
  annote =	{Keywords: Visibility in polygonal domains, shortest path in polygonal domains}
}

Keywords: Visibility in polygonal domains, shortest path in polygonal domains
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