5

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?

Oliver
  • 53

1 Answers1

5

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
Joseph O'Rourke
  • 149,182
  • 34
  • 342
  • 933