Generalized Voronoi diagrams for a ladder: II. Efficient construction of the diagram.

We present a collection of algorithms, all running in time o(n²log(n)log*(n)), for constructing a skeleton representation of a suitably generalised `Voronoi diagram' for a ladder moving in a 2-dimensional space bounded by plygonal barriers consisting of n line-segments. This diagram, which is a 2-dimensional subcomplex of the 3-dimensional configuration space of the ladder, is introducted and analyised in a companion paper by the present authors. The construction of the deagram described in this paper yields a motion-planning algorithm for the ladder which runs within the time-bound given above.