Next: MAXIMUM MAP LABELING Up: Miscellaneous Previous: MAXIMUM COMPATIBLE BINARY CONSTRAINT Index

### SHORTEST PATH MOTION IN 3 DIMENSIONS

- INSTANCE: Two points s,t and several polyhedral obstacles in three-dimensional Euclidean space.

- SOLUTION: A path from s to t that avoids the obstacles.

- MEASURE: The total length of the path in Euclidean metric.

- Good News: Admits an FPTAS [369] and [103].