One-to-one piecewise linear mappings over triangulations

Floater, Michael

doi:10.1090/S0025-5718-02-01466-7

One-to-one piecewise linear mappings over triangulations
HTML articles powered by AMS MathViewer

by Michael S. Floater PDF

Math. Comp. 72 (2003), 685-696 Request permission

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

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, DOI 10.1007/978-3-662-07233-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, DOI 10.1137/1.9781611971019
A. R. Collar, On the reciprocation of certain matrices, Proc. Roy. Soc. Edinburgh 59 (1939), 195–206. MR 8, DOI 10.1017/S0370164600012281
T. Duchamp, A. Certain, A. DeRose and W. Stuetzle, Hierarchical computation of PL harmonic embeddings, vol. preprint, 1997.
Peter Duren and Walter Hengartner, Harmonic mappings of multiply connected domains, Pacific J. Math. 180 (1997), no. 2, 201–220. MR 1487561, DOI 10.2140/pjm.1997.180.201
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.
Morgan Ward, Ring homomorphisms which are also lattice homomorphisms, Amer. J. Math. 61 (1939), 783–787. MR 10, DOI 10.2307/2371336
D. Field, Laplacian smoothing and Delaunay triangulation, Comm. Num. Meth. Eng. 4 (1988), 709–712.
Michael S. Floater, Parametrization and smooth approximation of surface triangulations, Comput. Aided Geom. Design 14 (1997), no. 3, 231–250. MR 1441192, DOI 10.1016/S0167-8396(96)00031-3
Michael S. Floater and Craig Gotsman, How to morph tilings injectively, J. Comput. Appl. Math. 101 (1999), no. 1-2, 117–129. MR 1664523, DOI 10.1016/S0377-0427(98)00202-7
Arieh Iserles, A first course in the numerical analysis of differential equations, Cambridge Texts in Applied Mathematics, Cambridge University Press, Cambridge, 1996. MR 1384977
H. Kneser, Lösung der Aufgabe 41, Jahresber. Deutsch. Math.-Verien. 35 (1926), 123–124.
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.
C. Wayne Mastin and Joe F. Thompson, Elliptic systems and numerical transformations, J. Math. Anal. Appl. 62 (1978), no. 1, 52–62. MR 478086, DOI 10.1016/0022-247X(78)90217-2
Ulrich Pinkall and Konrad Polthier, Computing discrete minimal surfaces and their conjugates, Experiment. Math. 2 (1993), no. 1, 15–36. MR 1246481, DOI 10.1080/10586458.1993.10504266
E. Praun, W. Sweldens, and P. Schröder, Consistent mesh parameterizations, Computer Graphics Proceedings, SIGGRAPH 01 (2001), 179–184.
Franco P. Preparata and Michael Ian Shamos, Computational geometry, Texts and Monographs in Computer Science, Springer-Verlag, New York, 1985. An introduction. MR 805539, DOI 10.1007/978-1-4612-1098-6
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, DOI 10.1007/978-1-4612-5282-5
T. Radó, Aufgabe 41, Jahresber. Deutsch. Math.-Verien. 35 (1926), 49.
W. T. Tutte, How to draw a graph, Proc. London Math. Soc. (3) 13 (1963), 743–767. MR 158387, DOI 10.1112/plms/s3-13.1.743
Richard S. Varga, Matrix iterative analysis, Second revised and expanded edition, Springer Series in Computational Mathematics, vol. 27, Springer-Verlag, Berlin, 2000. MR 1753713, DOI 10.1007/978-3-642-05156-2