Next: MINIMUM SIZE ULTRAMETRIC TREE Up: Miscellaneous Previous: MAXIMUM CHANNEL ASSIGNMENT Index

### 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 of points inside P with such that p0=s, pk=t, and, for all i with , the segment between pi and pi+1 is inside P.

- MEASURE: The Euclidean length of the path, i.e., where d denotes the Euclidean distance.

- Good News: Admits an FPTAS [357].