DEPARTMENT OF COMPUTER SCIENCE
DOCTORAL DISSERTATION DEFENSE


Candidate: Joonsoo Choi
Advisor: Chee-Keng Yap

Title: GEODESIC PROBLEMS IN HIGH DIMENSIONS
11:00 a.m., Monday, April 24, 1995
room 402, Warren Weaver Hall



Abstract

The geometric shortest path (geodesic) problem can be formulated as follows: given a collection of obstacles in $\R^d$ , and source and target points $s, t \in \R^d$, find a shortest obstacle-avoiding path between s and t. This thesis studies the Euclidean geodesic problem in $\R^3$ with polyhedral obstacles and the rectilinear geodesic problem in $\R^d$ with pairwise-disjoint, axes-parallel boxes.

Computing Euclidean geodesics in $\R^3$ with polyhedral obstacles is known to be NP-hard. In contrast, Papadimitriou gave a polynomial-time approximation algorithm for this problem. Unfortunately his complexity analysis involves an unusual mixture of both the algebraic computing model and the bit computing model. In the first part of the thesis, we present a true bit complexity analysis: there is an approximation algorithm that computes a geodesic with relative error $\epsilon > 0$ in $ O((n^3M\log{M} + (nM)^2) \cdot \mu(W)) $ time, where $M=O(nL/\epsilon)$, $W = O(\log(n/\epsilon)+L)$, and $\mu(W)$ is the time complexity of multiplying two W-bit integers. Our algorithm is a variant of Papadimitriou's algorithm.

The second part of the thesis addresses the rectilinear geodesic problem in $\R^3$ with a set of pairwise-disjoint, axes-parallel boxes. A monotonicity property of rectilinear geodesics is shown: every obstacle-avoiding geodesic between two points is monotone along at least one of coordinate directions. Using the monotonicity property of geodesics, an algorithm computing a geodesic from a query point to a fixed point is presented. The preprocessing time of the algorithm is $O(n^2 \log n)$ and each query takes $O(\log n +k)$ time, where k is the number of edges in a geodesic.

The last part of the thesis generalizes the above monotonicity property to every dimensions: given a set of pairwise-disjoint, axes-parallel boxes in $\R^d$, every obstacle-avoiding geodesic between two points is monotone along at least one of coordinate directions.