2026-07-23T22:06:47Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10007 2024-03-06T10:45:19Z ddc:004 open_access

Minimizing Distance-to-Sight in Polygonal Domains Oh, Eunjin Visibility in polygonal domains shortest path in polygonal domains 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Eunjin Oh 2018 Is Part Of LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2018.59 urn:nbn:de:0030-drops-100073 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.59 eng https://creativecommons.org/licenses/by/3.0/legalcode