5
$\begingroup$

I am curious about the following problem:

Given a polygon with holes and two convex subsets, $S$ and $T$, find points $s \in S, t \in T$ such that the shortest path between the two points has maximal length w.r.t. all point pairs in $S$ and $T$.

Note that both $s$ and $t$ might be interior points of the corresponding regions.

If $S$ would only be a point, i.e. the start point is fixed, we could build a Shortest Path Map (continuous Dijkstra) and could thereby find the farthest point.

Does anybody have any idea how to handle the case when $S$ is not just a point?

$\endgroup$
5
$\begingroup$

This* question is addressed in a 2010 paper,

Sang Won Bae, Matias Korman, Yoshio Okamoto. "The Geodesic Diameter of Polygonal Domains." (arXiv link)

They describe an algorithm that achieves a worst-case complexity of $O(n^{7.73})$ for a polygon of $n$ vertices, or $O(n^7 (\log n + h))$ when expressed also as a function of the number of holes $h$.

The reason the problem is so complicated is that the diameter-achieving points might lie in the interior of the polygon (i.e., not on its boundary). In that case, there are at least five distinct shortest paths, a result previously established for the geodesic diameter of convex polyhedra.

*The OP's question was changed slightly as I was preparing this answer, but I believe the added restriction to $S$ and $T$ does not make the problem any easier (in general).


Fig.1 from the Bae-Korman-Okamoto paper:
   enter image description here

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.