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.

REFERENCES

• 1: Hiromi Aonuma , Hiroshi Imai , Keiko Imai , Takeshi Tokuyama, Maximin location of convex objects in a polygon and related dynamic Voronoi diagrams, Proceedings of the sixth annual symposium on Computational geometry, p.225-234, June 07-09, 1990, Berkley, California, United States [doi>10.1145/98524.98575]
• 2: P. K. Agarwal , M. Sharir , P. Shor, Sharp upper and lower bounds on the length of general Davenport-Schinzel Sequences, Journal of Combinatorial Theory Series A, v.52 n.2, p.228-274, Nov. 1989 [doi>10.1016/0097-3165(89)90032-0]
• 3: Pankaj K. Agarwal , Micha Sharir , Sivan Toledo, Applications of parametric searching in geometric optimization, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.72-82, September 1992, Orlando, Florida, United States
• 4: Helmut Alt , Bernd Behrends , Johannes Blömer, Approximate matching of polygonal shapes (extended abstract), Proceedings of the seventh annual symposium on Computational geometry, p.186-193, June 10-12, 1991, North Conway, New Hampshire, United States [doi>10.1145/109648.109669]
• 5: Esther M. Arkin , L. Paul Chew , David P. Huttenlocher , Klara Kedem , Joseph S. B. Mitchell, An efficiently computable metric for comparing polygonal shapes, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.129-137, January 22-24, 1990, San Francisco, California, United States
• 6: Fu, J-J., and Lee, R.C.T., "Voronoi Diagrams of Moving Points in the Plane", Int. Journal of Computational Geometry ~ Applications, Vol 1(1), March 1991, pp. 23-32.
• 7: Leonidas J. Guibas , Joseph S. B. Mitchell, Voronoi Diagrams of Moving Points in the Plane, Proceedings of the 17th International Workshop, p.113-125, June 17-19, 1991
• 8: Leonidas Guibas , Jorge Stolfi, Primitives for the manipulation of general subdivisions and the computation of Voronoi, ACM Transactions on Graphics (TOG), v.4 n.2, p.74-123, April 1985 [doi>10.1145/282918.282923]
• 9: S Hart , M Sharir, Nonlinearity of Daveport:80Schinzel sequences and of generalized path compression schemes, Combinatorica, v.6 n.2, p.151-177, 1986 [doi>10.1007/BF02579170]
• 10: Daniel P. Huttenlocher , Klara Kedem, Computing the minimum Hausdorff distance for point sets under translation, Proceedings of the sixth annual symposium on Computational geometry, p.340-349, June 07-09, 1990, Berkley, California, United States [doi>10.1145/98524.98599]
• 11: Daniel P. Huttenlocher , Klara Kedem , Micha Sharir, The upper envelope of Voronoi surfaces and its applications, Proceedings of the seventh annual symposium on Computational geometry, p.194-203, June 10-12, 1991, North Conway, New Hampshire, United States [doi>10.1145/109648.109670]
• 12: Mumford, D., "The problem of robust shape descriptors'', First International Conference on Computer Vision, 1987, pp. 602-606.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

General Terms:
Algorithms, Theory