Available in electronic format
Available in print format		 Mathematics of Computation
Journal of the American Mathematical Society
ISSN 1088-6842(e) ISSN 0025-5718(p)
Previous issue | Table of contents | Next issue
Articles in press | Recently posted articles | Most recent issue | All issues
Previous Article | Next Article
     

One-to-one piecewise linear mappings over triangulations

Author(s): Michael S. Floater.
Journal: Math. Comp. 72 (2003), 685-696.
MSC (2000): Primary 65N30, 58E20; Secondary 05C85, 65M50
Posted: October 17, 2002
Retrieve article in: PDF DVI PostScript

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:

[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
Email: mif@math.sintef.no

DOI: 10.1090/S0025-5718-02-01466-7
PII: S 0025-5718(02)01466-7
Keywords: Triangulation, harmonic map, maximum principle, parameterization, numerical grid generation, planar embedding
Received by editor(s): July 9, 2001
Posted: October 17, 2002
Copyright of article: Copyright 2002, American Mathematical Society

  AMS Website Logo Small Comments: webmaster@ams.org
© Copyright 2008, American Mathematical Society
Privacy Statement 		Search the AMSPowered by Google