On the Complexity of Constrained Distance Transforms and Digital Distance Map Updates in Two Dimensions
Terrance E. Boult
- On the Complexity of Constrained Distance Transforms and Digital Distance Map Updates in Two Dimensions
- Boult, Terrance E.
- Technical reports
- Computer Science
- Permanent URL:
- Columbia University Computer Science Technical Reports
- Part Number:
- Department of Computer Science, Columbia University
- Publisher Location:
- New York
- Using digital distance maps, one can easily solve the shortest path problem from any point by simply following the gradient of the distance map. Other researchers have developed techniques to quickly compute such maps. One such technique, the constrained distance transform, is described and a computational complexity analysis is presented. Unfortunately, algorithms for digital distance maps have all assumed a static environment. This paper extends the usefulness of the planar digital distance maps by providing an efficient means for dealing with obstacles in motion. In particular, an algorithm is presented that allows one to compute what portions of a map will probably be effected by an obstacle's motion. The regions that must be checked for possible update when an obstacle moves are those that are in its "shadow", or in the shadow of obstacles that are partially in the shadow of the moving obstacle. The technique can handle multiple fixed goals, multiple obstacles moving and interacting in an arbitrary fashion. A complexity analysis and short verification is presented. The algorithm is demonstrated on a number of synthetic two dimensional examples, and example timing results are reported.
- Computer science
- Item views: