The Minimum Bends Path Problem in Three Dimensions
David Wagner
Dartmouth University


Date: Friday September 03, 2004
Time 11-12
Venue: Room  3464 

Abstract
In this talk we consider the Rectilinear Minimum 
Bends Path Problem among Rectilinear Obstacles in 
Three Dimensions. The problem is well studied in 
two dimensions, but is relatively unexplored
in higher dimensions.

We give an algorithm which solves the problem in worst-case
$O(\beta n\log n)$ time, where $n$ is the number of corners among
all obstacles, and $\beta$ is the size of a BSP decomposition of
obstacle space.  It has been shown that in the worst case
$\beta = \Theta(n^{3/2})$, giving
us an overall worst case time of $O(n^{5/2}\log n)$.  However
in many circumstances we will have $\beta \approx O(n)$.
Previously known algorithms have a worst-case
running time of $O(n^3)$.