On Romeo and Juliet Problems: Minimizing Distance-to-Sight
| Autor: | Ahn, Hee-Kap, Oh, Eunjin, Schlipf, Lena, Stehn, Fabian, Strash, Darren |
|---|---|
| Rok vydání: | 2019 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | 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 they 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 $s,t$ where the two persons start. Comment: 12 pages, 8 figures; appeared in Proc. 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018) |
| Databáze: | arXiv |
| Externí odkaz: |
|