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

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

0.00 Avg rating0 Votes
Article ID: iaor20002359
Country: Japan
Volume: 42
Issue: 1
Start Page Number: 45
End Page Number: 58
Publication Date: Mar 1999
Journal: Journal of the Operations Research Society of Japan
Authors: , ,
Keywords: programming: geometric, programming: parametric
Abstract:

This paper considers the maximin placement of a convex polygon P inside a polygon Q, and introduces 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 O(m416(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 O(mn log mn) time. The problem of placing multiple translates of P inside Q in a maximin manner is also considered.

Reviews

Required fields are marked *. Your email address will not be published.