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

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.