Shortest Path amidst Disc Obstacles is Computable

the exact combinatorial shortest path
between two points $p,q$ amidst a collection
of $n$ discs is computable, provided
the radii of the discs are rationally related.

The numerical input data are assumed to be
represented by algebraic numbers.
In fact, we show a single exponential time bound when the
input are all rational numbers.

This appears to be one of the first example of a
non-algebraic combinatorial problem which is shown computable.

Our result depend on effective
bounds from transcendental number theory.
Extensions of this result when the radii
are arbitrary algebraic numbers will be indicated.

Joint work with Ee-Chien Chang, Sung Woo Choi, DoYong Kwon
and Hyungju Park.