Veröffentlichung

Titel:

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

AutorInnen:

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

Kategorie:

Konferenzbandbeiträge

erschienen in:

Proceedings of the 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT'18), 2018

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.

Download:

DROPS

BibTeX-Eintrag:

@inproceedings{, 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-Sigh }, booktitle = {Proceedings of the 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT'18)}, year = {2018}, }