On Romeo and Juliet problems: minimizing distance-to-sight

DOI10.1016/J.COMGEO.2019.07.003MaRDI QIDQ2331220zbMATH OpenOpenAlexFDO

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

Publication date 25 October 2019

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1906.01114, https://drops.dagstuhl.de/opus/volltexte/2018/8832/

zbMATH Keywords

shortest pathvisibility polygonwatchman problems

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

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 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(lo{g}^{2}n)$ time for any two query positions $s,t$ where the two persons start.

Recommendations

• On Romeo and Juliet problems: minimizing distance-to-sight
• Can Romeo and Juliet meet? Or rendezvous games with adversaries on graphs
• Can Romeo and Juliet meet? Or rendezvous games with adversaries on graphs
• Minimizing Distance-to-Sight in Polygonal Domains
• A note on a maximum distance problem
• The rectilinear distance minisum problem with minimum distance constraints:
• scientific article; zbMATH DE number 4035743
• The distance matching problem
• The rendezvous problem on discrete locations

Cites work

• A new data structure for shortest path queries in a simple polygon
• A Pedestrian Approach to Ray Shooting: Shoot a Ray, Take a Walk
• Approximating watchman routes
• Finding the shortest watchman route in a simple polygon
• Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
• Optimal shortest path queries in a simple polygon
• Optimum watchman routes
• Quickest visibility queries in polygonal domains
• Shortest path to a segment and quickest visibility queries
• Touring a sequence of polygons
• Watchman tours for polygons with holes

Cited in

(2)

• Minimizing Distance-to-Sight in Polygonal Domains
• On Romeo and Juliet problems: minimizing distance-to-sight

This page was built for publication: On Romeo and Juliet problems: minimizing distance-to-sight

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2331220)