Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 

 

One-to-one piecewise linear mappings over triangulations


Author: Michael S. Floater
Journal: Math. Comp. 72 (2003), 685-696
MSC (2000): Primary 65N30, 58E20; Secondary 05C85, 65M50
Published electronically: October 17, 2002
MathSciNet review: 1954962
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We call a piecewise linear mapping from a planar triangulation to the plane a convex combination mapping if the image of every interior vertex is a convex combination of the images of its neighbouring vertices. Such mappings satisfy a discrete maximum principle and we show that they are one-to-one if they map the boundary of the triangulation homeomorphically to a convex polygon. This result can be viewed as a discrete version of the Radó-Kneser-Choquet theorem for harmonic mappings, but is also closely related to Tutte's theorem on barycentric mappings of planar graphs.


References [Enhancements On Off] (What's this?)

  • [1] Dietrich Braess, Finite elements, Cambridge University Press, Cambridge, 1997. Theory, fast solvers, and applications in solid mechanics; Translated from the 1992 German original by Larry L. Schumaker. MR 1463151
  • [2] José E. Castillo (ed.), Mathematical aspects of numerical grid generation, Frontiers in Applied Mathematics, vol. 8, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1991. MR 1109544
  • [3] Gustave Choquet, Sur un type de transformation analytique généralisant la représentation conforme et définie au moyen de fonctions harmoniques, Bull. Sci. Math. (2) 69 (1945), 156–165 (French). MR 0016973
  • [4] T. Duchamp, A. Certain, A. DeRose and W. Stuetzle, Hierarchical computation of PL harmonic embeddings, vol. preprint, 1997.
  • [5] Peter Duren and Walter Hengartner, Harmonic mappings of multiply connected domains, Pacific J. Math. 180 (1997), no. 2, 201–220. MR 1487561, 10.2140/pjm.1997.180.201
  • [6] M. Eck, T. DeRose, T. Duchamp, H. Hoppe, M. Lounsbery, and W. Stuetzle, Multiresolution analysis of arbitrary meshes, Computer Graphics Proceedings, SIGGRAPH 95 (1995), 173-182.
  • [7] István Fáry, On straight line representation of planar graphs, Acta Univ. Szeged. Sect. Sci. Math. 11 (1948), 229–233. MR 0026311
  • [8] D. Field, Laplacian smoothing and Delaunay triangulation, Comm. Num. Meth. Eng. 4 (1988), 709-712.
  • [9] Michael S. Floater, Parametrization and smooth approximation of surface triangulations, Comput. Aided Geom. Design 14 (1997), no. 3, 231–250. MR 1441192, 10.1016/S0167-8396(96)00031-3
  • [10] Michael S. Floater and Craig Gotsman, How to morph tilings injectively, J. Comput. Appl. Math. 101 (1999), no. 1-2, 117–129. MR 1664523, 10.1016/S0377-0427(98)00202-7
  • [11] Arieh Iserles, A first course in the numerical analysis of differential equations, Cambridge Texts in Applied Mathematics, Cambridge University Press, Cambridge, 1996. MR 1384977
  • [12] H. Kneser, Lösung der Aufgabe 41, Jahresber. Deutsch. Math.-Verien. 35 (1926), 123-124.
  • [13] A. W. F. Lee, W. Sweldens, P. Schröder, L. Cowsar, and D. Dobkin, MAPS: Multiresolution adaptive parameterization of surfaces, Computer Graphics Proceedings, SIGGRAPH 98 (1998), 95-104.
  • [14] C. Wayne Mastin and Joe F. Thompson, Elliptic systems and numerical transformations, J. Math. Anal. Appl. 62 (1978), no. 1, 52–62. MR 478086, 10.1016/0022-247X(78)90217-2
  • [15] Ulrich Pinkall and Konrad Polthier, Computing discrete minimal surfaces and their conjugates, Experiment. Math. 2 (1993), no. 1, 15–36. MR 1246481
  • [16] E. Praun, W. Sweldens, and P. Schröder, Consistent mesh parameterizations, Computer Graphics Proceedings, SIGGRAPH 01 (2001), 179-184.
  • [17] Franco P. Preparata and Michael Ian Shamos, Computational geometry, Texts and Monographs in Computer Science, Springer-Verlag, New York, 1985. An introduction. MR 805539
  • [18] Murray H. Protter and Hans F. Weinberger, Maximum principles in differential equations, Springer-Verlag, New York, 1984. Corrected reprint of the 1967 original. MR 762825
  • [19] T. Radó, Aufgabe 41, Jahresber. Deutsch. Math.-Verien. 35 (1926), 49.
  • [20] W. T. Tutte, How to draw a graph, Proc. London Math. Soc. (3) 13 (1963), 743–767. MR 0158387
  • [21] Richard S. Varga, Matrix iterative analysis, Second revised and expanded edition, Springer Series in Computational Mathematics, vol. 27, Springer-Verlag, Berlin, 2000. MR 1753713

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 65N30, 58E20, 05C85, 65M50

Retrieve articles in all journals with MSC (2000): 65N30, 58E20, 05C85, 65M50


Additional Information

Michael S. Floater
Affiliation: SINTEF Applied Mathematics, P.O. Box 124 Blindern, 0314 Oslo, Norway
Email: mif@math.sintef.no

DOI: http://dx.doi.org/10.1090/S0025-5718-02-01466-7
Keywords: Triangulation, harmonic map, maximum principle, parameterization, numerical grid generation, planar embedding
Received by editor(s): July 9, 2001
Published electronically: October 17, 2002
Article copyright: © Copyright 2002 American Mathematical Society