On overlays and minimization diagrams

ABSTRACT

The overlay of 2≤m≤d minimization diagrams of n surfaces in R^d is isomorphic to a substructure of a suitably constructed minimization diagram of mn surfaces in R^d+m−1. This elementary observation leads to a new bound on the complexity of the overlay of minimization diagrams of collections of d-variate semi-algebraic surfaces, a tight bound on the compleity of the overlay of minimization diagrams of collections of hyperplanes, and faster algorithms for constructing such overlays. Further algoithmic implications are discussed.

REFERENCES

• 1: P. K. Agarwal, B. Aronov, S. Har-Peled, and M. Sharir. Approximation and exact algorithms for minimum-width annuli and shells. Discrete Comput. Geom., 24(4):687--705, 2000.
• 2: Pankaj K. Agarwal , Boris Aronov , Micha Sharir, Computing Envelopes in Four Dimensions with Applications, SIAM Journal on Computing, v.26 n.6, p.1714-1732, Dec. 1997 [doi>10.1137/S0097539794265724]
• 3: P. K. Agarwal, B. Aronov, and M. Sharir. Exact and approximation algorithms for minimum-width cylindrical shells. Discrete Comput. Geom., 26:307--320, 2001.
• 4: P. K. Agarwal, O. Schwarzkopf, and M. Sharir. The overlay of lower envelopes and its applications. Discrete Comput. Geom., 15:1--13, 1996.
• 5: P. K. Agarwal and M. Sharir. Arrangements and their applications. In J.-R. Sack and J. Urrutia, editors, Handbook of Computational Geometry, pages 49--119. Elsevier Science Publishers B.V. North-Holland, Amsterdam, 2000.
• 6: S. Basu, R. Pollack, and M.-F. Roy. Algorithms in Real Algebraic Geometry. Springer Verlag, Berlin, 2003.
• 7: Paul J. Besl , Neil D. McKay, A Method for Registration of 3-D Shapes, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.14 n.2, p.239-256, February 1992 [doi>10.1109/34.121791 ]
• 8: T. M. Chan. Approximating the diameter, width, smallest enclosing cylinder and minimum-width annulus. Internat. J. Comput. Geom. Appl., 12(2):67--85, 2002.
• 9: B. Chazelle. An optimal convex hull algorithm in any fixed dimension. Discrete Comput. Geom., 10:377--409, 1993.
• 10: Kenneth L. Clarkson, A randomized algorithm for closest-point queries, SIAM Journal on Computing, v.17 n.4, p.830-847, August 1988 [doi>10.1137/0217052]
• 11: Christian A. Duncan , Michael T. Goodrich , Edgar A. Ramos, Efficient approximation and optimization algorithms for computational metrology, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.121-130, January 05-07, 1997, New Orleans, Louisiana, United States
• 12: H. Ebara, N. Fukuyama, H. Nakano, and Y. Nakanishi. Roundness algorithms using the Voronoi diagrams. In Abstracts 1st Canad. Conf. Comput. Geom., page 41, 1989.
• 13: H. Edelsbrunner. The upper envelope of piecewise linear functions: Tight complexity bounds in higher dimensions. Discrete Comput. Geom., 4:337--343, 1989.
• 14: Herbert Edelsbrunner , Raimund Seidel, Voronoi diagrams and arrangements, Discrete & Computational Geometry, v.1 n.1, p.25-44, 1986 [doi>10.1007/BF02187681]
• 15: E. Ezra and M. Sharir. Bounds for the ICP algorithm. These proceedings, 2005.
• 16: L. J. Guibas, D. Halperin, J. Matoušek, and M. Sharir. On vertical decomposition of arrangements of hyperplanes in four dimensions. Discrete Comput. Geom., 14:113--122, 1995.
• 17: V. Koltun and M. Sharir. The partition technique for overlays of envelopes. SIAM J. Comput., 32:841--863, 2003.
• 18: Vladlen Koltun , Carola Wenk, Matching Polyhedral Terrains Using Overlays of Envelopes, Algorithmica, v.41 n.3, p.159-183, January 2005 [doi>10.1007/s00453-004-1107-0]
• 19: P. McMullen. The maximal number of faces of a convex polytope. Mathematika, 17:179--184, 1970.
• 20: M. Sharir. Almost tight upper bounds for lower envelopes in higher dimensions. Discrete Comput. Geom., 12:327--345, 1994.
• 21: Micha Sharir , Pankaj K. Agarwal, Davenport-Schinzel sequences and their geometric applications, Cambridge University Press, New York, NY, 1996
• 22: G. M. Ziegler. Lectures on Polytopes, volume 152 of Graduate Texts in Mathematics. Springer-Verlag, New York, 1995. Revised edition 1998.

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

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.0 General

General Terms:
Algorithms, Theory

Keywords:
Voronoi diagrams, arrangements, hyperplanes, lower envelopes, minimization diagrams, overlays, power diagrams