Shortest Paths Among Dynamic Obstacles

It appears your Web browser is not configured to display PDF files. Download adobe Acrobat or click here to download the PDF file.

Click here to download the PDF file.


Nourisagharlou, Arash




The problem of collision-free motion planning in dynamic environments has received considerable attention in computational geometry. In this thesis, we study the point robot motion planning problems among dynamic obstacles. A growing disc is a disc obstacle that grows over time. A transient obstacle is an obstacle that appears at a particular time in the environment and may disappear at some later time. In the first part of this thesis, we study the problem of computing collision-free shortest paths among growing discs. This problem has previously been studied for discs where the growth rates are fixed. We study a more general problem variant, where: (1) the speeds at which the discs grow are polynomial functions of degree β and (2) the source and destination points are given as query points. We show how to preprocess a set ofgrowing discs so that, for two given query points s and d, a shortest path from s to d can be computed in O(n2 log(βn)) time. The preprocessing time of our algorithm is O(n2 log n + k log k) where k is the number of intersections between the growing discs and the tangent paths (straight line paths that touch the boundaries of a pair of growing discs). We also establish an upper bound of O(n3β) on k.

In the second part of the thesis, we study the problem of computing collision-free shortest paths among transient obstacles. First, we design an optimal Θ(n log n) algorithm for determining time-minimal rectilinear paths among n non-intersecting transient rectilinear obstacles. Next, we consider the variant of the shortest path problem among transient obstacles where the metric used to measure distances is Euclidean and the obstacles are non-intersecting polygons. We present an O(n2 log n) time algorithm for computing the Euclidean shortest path map among transient polygonal obstacles in the plane. This improves the time complexity of the existing algorithm by a factor of n. We show that the shortest path map contains Ω(n2) cells, and thus, proving that our algorithm is nearly optimal.


Computer Science




Carleton University

Thesis Degree Name: 

Doctor of Philosophy: 

Thesis Degree Level: 


Thesis Degree Discipline: 

Computer Science

Parent Collection: 

Theses and Dissertations

Items in CURVE are protected by copyright, with all rights reserved, unless otherwise indicated. They are made available with permission from the author(s).