MINIMUM K-LINK PATH IN A POLYGON

• INSTANCE: Polygon P with n integer-coordinates vertices and two points s and t in P.

• SOLUTION: A k-link path between s and t, i.e., a sequence $p_0, \ldots, p_h$ of points inside P with $h \leq k$ such that $p_0=s$, $p_k=t$, and, for all i with $0 \leq i < h$, the segment between $p_i$ and $p_{i+1}$ is inside P.

• MEASURE: The Euclidean length of the path, i.e., $\sum_{i=0}^{h-1} d(p_i,p_{i+1})$ where d denotes the Euclidean distance.

  
  

• Good News: Admits an FPTAS [377].