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 [390] and [111].