On dynamic Voronoi diagrams and the minimum Hausdorff distance for point sets under Euclidean motion in the plane

Abstract

We show that the dynamic Voronoi diagram of k sets of points in the plane, where each set consists of m points moving rigidly, has complexity O(n2k2&lgr;s(k)) for some fixed s, where &lgr;s(n) is the maximum length of a (n, s) Davenport-Schinzel sequence. This improves the result of Aonuma et al., who show an upper bound of O(n3k4 log* k) for the complexity of such Voronoi diagrams. We then apply this result to the problem of finding the minimum Hausdorff distance between two point sets in the plane under Euclidean motion. We show that this distance can be computed in time O((m + n)6 log (mn)), where the two sets contain m and n points respectively.