Computational Geometry Seminar

"The Three-Phase Method and Applications" (T. Biedl)
The three-phase method is a generic method for creating orthogonal drawings of graphs of arbitrarily high degree. Among its advantages are the following: simplification of implementation, modularization of a larger problem, easier development of new algorithms, flexibility of adaptation of algorithms to additional constraints, and others. We will present this method and some of its applications.

"Shortest Paths of Bounded Curvature in a Convex Polygon" (S. Lazard)
I will review some results found during the Workshop on Bounded Radius of Curvature Problems at the Bellairs Research Institute of McGill University, March 9 to 16, 1997.
We address the problem of finding a shortest path of bounded curvature in a convex polygon. More precisely, given prescribed initial and final configurations (i.e., positions and direction headings) and a convex polygon, we want to compute (if it exists) a shortest C¹ path (i.e., continuously differentiable path) joining those two configurations inside the convex polygon, with the further constraint that, on each C² piece, the radius of curvature is at least 1. If there is no such path, we want to report that fact. A path of bounded curvature can be viewed as the trace of the middle of the rear axle of a vehicle moving forward that has a minimum turning radius equal to 1. We present an O(n*log² n) time algorithm to solve this problem, where n is the number of edges of the polygon.