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

[For part I of this paper see Commun. Pure Appl. Math. 39, 423-483 (1986; Zbl 0601.51025.] The paper discusses the construction of a generalized Voronoi diagram for two-dimensional space of n lines and vertices. It is shown that the size of the Voronoi diagram is \(O(n^ 2 \alpha (n)^{O(\alpha (n)^ s)})\) for some fixed integer s, where \(\alpha\) (n) is the inverse of Ackermann's function. Also shown in the paper is the construction of this Voronoi diagram in time \(O(n^ 2 \log n \alpha (n)^{O(\alpha (n)^ s)})\). The results are obtained by case analysis of the vertices in the Voronoi diagram. This generalized Voronoi diagram can be used for a motion-planning algorithm for the ladder-moving problem in a two-dimensional space with polygonal barriers consisting with the same time complexity. Recently, there is a combinatorial result by \textit{P. Agarwal}, \textit{M. Sharir}, and \textit{P. Shor}, ``Sharp upper and lower bounds on the length of general Davenport-Schinzel sequences'', which implicitly improves the bound given in this paper.