Next: MINIMUM SIZE ULTRAMETRIC TREE
Previous: MAXIMUM CHANNEL ASSIGNMENT
Polygon P with n integer-coordinates vertices and two points s and t
A k-link path between s and t, i.e., a sequence
points inside P with
such that ,
and, for all i
the segment between
is inside P.
The Euclidean length of the path, i.e.,
where d denotes the Euclidean distance.
- Good News:
Admits an FPTAS .