Building triangulations using ε-nets

ABSTRACT

This work addresses the problem of approximating a manifold by a simplicial mesh, and the related problem of building triangulations for the purpose of piecewise-linear approximation of functions. It has long been understood that the vertices of such meshes or triangulations should be "well-distributed," or satisfy certain "sampling conditions." This work clarifies and extends some algorithms for finding such well-distributed vertices, by showing that they can be regarded as finding ε-nets or Delone sets in appropriate metric spaces. In some cases where such Delone properties were already understood, such as for meshes to approximate smooth manifolds that bound convex bodies, the upper and lower bound results are extended to more general manifolds; in particular, under some general conditions, the minimum Hausdorff distance for a mesh with n simplices to a d-manifold M is Θ((∫_{M√|κ(x)|/n)}^2/d) as n ⋺ ∞, where κ(x) is the Gaussian curvature at point x ∈ M. We also relate these constructions to Dudley's approximation scheme for convex bodies, which can be interpreted as involving an ε-net in a metric space whose distance function depends on surface normals.

REFERENCES

• 1: P. Agarwal, S. Har-Peled, and K. Varadarajan. Geometric approximation via coresets. In E. Welzl, editor, Current Trends in Combinatorial and Computational Geometry. Cambridge University Press, 2005.
• 2: N. Amenta, S. Choi, and R. Kolluri. The power crust, unions of balls, and the medial axis transform. Computational Geometry: Theory and Applications, 19:127--153, 2001.
• 3: Vijay Arya , Naveen Garg , Rohit Khandekar , Kamesh Munagala , Vinayaka Pandit, Local search heuristic for k-median and facility location problems, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.21-29, July 2001, Hersonissos, Greece [doi>10.1145/380752.380755]
• 4: L. Chen, P. Sun, and J. Xu. Optimal anisotropic simplicial meshes for minimizing interpolation errors in lp-norm. Math. Comp., To Appear.
• 5: P. T. Chruściel, J. Fu, G. Galloway, and R. E. Howard. On fine differentiability properties of horizons and applications to Riemannian geometry. J. Geometry and Physics, 41:1--12, 2002.
• 6: Kenneth L. Clarkson, An algorithm for approximate closest-point queries, Proceedings of the tenth annual symposium on Computational geometry, p.160-164, June 06-08, 1994, Stony Brook, New York, United States [doi>10.1145/177424.177609]
• 7: David Cohen-Steiner , Pierre Alliez , Mathieu Desbrun, Variational shape approximation, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004
• 8: C. D. Cutler. A review of the theory and estimation of fractal dimension. In H. Tong, editor, Dimension Estimation and Models. World Scientific, 1993.
• 9: Qiang Du , Vance Faber , Max Gunzburger, Centroidal Voronoi Tessellations: Applications and Algorithms, SIAM Review, v.41 n.4, p.637-676, Dec. 1999 [doi>10.1137/S0036144599352836]
• 10: R. M. Dudley. Metric entropy of some classes of sets with differentiable boundaries. J. Approximation Theory, 10:227--236, 1974.
• 11: Y. Eldar, M. Lindenbaum, M. Porat, and Y. Zeevi. The farthest point strategy for progressive image sampling, 1997.
• 12: J. Erickson. Personal Communication.
• 13: T. Gonzalez. Clustering to minimize the maximum intercluster distance. Theoret. Comput. Sci., 38:293--306, 1985.
• 14: P. M. Gruber. Asymptotic estimates for best and stepwise approximation of convex bodies I. Forum Math., 5:281--297, 1993.
• 15: P. M. Gruber. Optimum quantization and its applications. Adv. Math., 186:456--497, 2004.
• 16: Paul S. Heckbert , Michael Garland, Optimal triangulation and quadric-based surface simplification, Computational Geometry: Theory and Applications, v.14 n.1-3, p.49-65, Nov. 1999 [doi>10.1016/S0925-7721(99)00030-9]
• 17: Greg Leibon , David Letscher, Delaunay triangulations and Voronoi diagrams for Riemannian manifolds, Proceedings of the sixteenth annual symposium on Computational geometry, p.341-349, June 12-14, 2000, Clear Water Bay, Kowloon, Hong Kong [doi>10.1145/336154.336221]
• 18: M. Ludwig. Asymptotic approximation of convex curves; the Hausdorff metric case. Arch. Math., 70:331--336, 1998.
• 19: E. Nadler. Piecewise linear best l2 approximation on triangulations. In C. K. Chui, L. L. Schumaker, and J. D. Ward, editors, Approximation Theory V, pages 499--502. Academic Press, 1986.
• 20: G. Peyré and L. D. Cohen. Geodesic computations for fast and accurate surface remeshing and parameterization. Progress in Nonlinear Differential Equations and Their Applications, 63:157--171, 2005.
• 21: H. Pottmann, R. Krasauskas, B. Hamann, K. Joy, and W. Seibold. On piecewise linear approximation of quadratic functions. J. Geom. Graphics, 4:31--53, 2000.
• 22: H. Pottmann, T. Steiner, M. Hofer, C. Haider, and A. Hanbury. The isophotic metric and its application to feature sensitive morphology on surfaces. In T. Pajdla and J. Matas, editors, Computer Vision --- ECCV 2004, Part IV, volume 3024 of Lecture Notes in Computer Science, pages 560--572. Springer, 2004.
• 23: J. R. Shewchuk. What is a good linear finite element? Interpolation, conditioning, anisotropy, and quality measures. http://www.cs.berkeley.edu/~jrs/papers/elemj.pdf, 2002.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation
          Subjects: Approximation of surfaces and contours

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation
          Subjects: Spline and piecewise polynomial approximation

General Terms:
Theory

Keywords:
Delone, curvature, manifolds, meshes