Remote Access Mathematics of Computation
Green Open Access

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

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] D. Braess, Finite elements, Cambridge University Press, Cambridge, 1997. MR 98f:65002
  • [2] J. E. Castillo (ed.), Mathematical Aspects of Numerical Grid Generation, SIAM, 1991. MR 92h:65148
  • [3] G. Choquet, Sur un type de transformation analytique généralisant la représentation conforme et définé au moyen de fonctions harmoniques, Bull. Sci. Math. 69 (1945), 156-165. MR 8:93a
  • [4] T. Duchamp, A. Certain, A. DeRose and W. Stuetzle, Hierarchical computation of PL harmonic embeddings, vol. preprint, 1997.
  • [5] P. Duren and W. Hengartner, Harmonic mappings of multiply connected domains, Pac. J. Math. 180 (1997), 201-220. MR 99f:30051
  • [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] I. Fáry, On straight line representations of planar graphs, Acta Sci. Math. Szeged 11 (1948), 229-233. MR 10:136f
  • [8] D. Field, Laplacian smoothing and Delaunay triangulation, Comm. Num. Meth. Eng. 4 (1988), 709-712.
  • [9] M. S. Floater, Parametrization and smooth approximation of surface triangulations, Comp. Aided Geom. Design 14 (1997), 231-250. MR 98a:65018
  • [10] M. S. Floater and C. Gotsman, How to morph tilings injectively, J. Comp. Appl. Math. 101 (1999), 117-129. MR 99k:52032
  • [11] A. Iserles, A first course in numerical analysis of differential equations, Cambridge University Press, Cambridge, 1996. MR 97m:65003
  • [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. W. Mastin and J. F. Thompson, Elliptic systems and numerical transformations, J. Math. Anal. Appl. 62 (1978), 52-62. MR 80i:65134
  • [15] U. Pinkall and K. Polthier, Computing Discrete Minimal Surfaces and Their Conjugates, Exp. Math. 2 (1993), 15-36. MR 94j:53009
  • [16] E. Praun, W. Sweldens, and P. Schröder, Consistent mesh parameterizations, Computer Graphics Proceedings, SIGGRAPH 01 (2001), 179-184.
  • [17] F. P. Preparata and M. I. Shamos, Computational geometry, Springer, New York, 1985. MR 87d:68102
  • [18] M. H. Protter and H. F. Weinberger, Maximum principles in differential equations, Springer, New York, 1984. MR 86f:35034
  • [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. 13 (1963), 743-768. MR 28:1610
  • [21] R. S. Varga, Matrix iterative analysis, Springer, New York, 2000. MR 2001g:65002

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

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

American Mathematical Society