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 α (n) ^o(α(n)3)) for some fixed integer s(where α(n) is the inverse Ackermann's function), for constructing a skeleton representation of a suitably generalized "Voronoi diagram" for a ladder moving in a two-dimensional space bounded by polygonal barriers consisting of n line segments. This diagram, which is a two-dimensional subcomplex of the dimensional configuration space of the ladder, is introduced and analyzed in a companion paper by the present authors. The construction of the diagram described in this paper yields a motion-planning algorithm for the ladder which runs within the same time bound given above.