Home

On the Complexity of Constrained Distance Transforms and Digital Distance Map Updates in Two Dimensions

Terrance E. Boult

Title:
On the Complexity of Constrained Distance Transforms and Digital Distance Map Updates in Two Dimensions
Author(s):
Boult, Terrance E.
Date:
Type:
Technical reports
Department:
Computer Science
Permanent URL:
Series:
Columbia University Computer Science Technical Reports
Part Number:
CUCS-454-89
Publisher:
Department of Computer Science, Columbia University
Publisher Location:
New York
Abstract:
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.
Subject(s):
Computer science
Item views:
95
Metadata:
text | xml

In Partnership with the Center for Digital Research and Scholarship at Columbia University Libraries/Information Services | Terms of Use