Maximin location of convex objects in a polygon and related dynamic Voronoi diagrams

Abstract

This paper considers the maximin placement of a convex polygon P inside a polygon Q, and introduce several new static and dynamic Voronoi diagrams to solve the problem. It is shown that P can be placed inside Q, using translation and rotation, so that the minimum Euclidean distance between any point on P and any point on Q is maximized in Ο(m4n λ16(mn) log mn) time, where m and n are the numbers of edges of P and Q, respectively, and λ16(N) is the maximum length of Davenport-Schinzel sequences on N alphabets of order 16. If only translation is allowed, the problem can be solved in Ο(mn log mn) time. The problem of placing multiple translates of P inside Q in a maximum manner is also considered, and in connection with this problem the dynamic Voronoi diagram of κ rigidly moving sets of n points is investigated. The combinatorial complexity of this canonical dynamic diagram for κn points is shown to be Ο(n2) and Ο(n3κ4 log* κ) for κ = 2, 3 and κ ≥ 4, respectively. Several related problems are also treated in a unified way.