Path planning in the presence of vertical obstacles

Consideration is given to the problem of finding a shortest path between two points in 3-D space with a restricted class of polyhedral obstacles (vertical buildings with a fixed number k of distinct heights). For the case when all the obstacles have equal heights, a shortest-path algorithm is presented with complexity O(n ²), i.e. the same complexity as for the 2-D case (n is the total number of corners in all the obstacles). For the general case (k distinct heights), an algorithm is presented for finding a shortest path in time O(n^6k-1). Also presented is an O( n²) approximation algorithm that finds paths that are, at most, 8% longer than the shortest path for the case of k distinct heights when certain minimum separation requirements are satisfied, and a description is given of how the approximation algorithm can be extended to the general case (arbitrary separations)