A Dubins path is a shortest path with bounded curvature. The seminal result in non-holonomic motion planning is that (in the absence of obstacles) a Dubins path consists either from a circular arc followed by a segment followed by another arc, or fro
m three circular arcs [Dubins, 1957]. Dubins original proof uses advanced calculus; later, Dubins result was reproved using control theory techniques [Reeds and Shepp, 1990], [Sussmann and Tang, 1991], [Boissonnat, Cerezo, and Leblond, 1994]. We introduce and study a discrete analogue of curvature-constrained motion. We show that shortest bounded-curvature polygonal paths have the same structure as Dubins paths. The properties of Dubins paths follow from our results as a limiting case---this gives a new, discrete proof of Dubins result.
We provide an O(log log OPT)-approximation algorithm for the problem of guarding a simple polygon with guards on the perimeter. We first design a polynomial-time algorithm for building epsilon-nets of size O(1/epsilon log log 1/epsilon) for the insta
nces of Hitting Set associated with our guarding problem. We then apply the technique of Bronnimann and Goodrich to build an approximation algorithm from this epsilon-net finder. Along with a simple polygon P, our algorithm takes as input a finite set of potential guard locations that must include the polygons vertices. If a finite set of potential guard locations is not specified, e.g. when guards may be placed anywhere on the perimeter, we use a known discretization technique at the cost of making the algorithms running time potentially linear in the ratio between the longest and shortest distances between vertices. Our algorithm is the first to improve upon O(log OPT)-approximation algorithms that use generic net finders for set systems of finite VC-dimension.
