Convex combination maps over triangulations, tilings, and tetrahedral meshes
- PDF / 311,517 Bytes
- 10 Pages / 595 x 842 pts (A4) Page_size
- 83 Downloads / 203 Views
Springer 2006
Convex combination maps over triangulations, tilings, and tetrahedral meshes Michael S. Floater a and Valérie Pham-Trong b a Centre of Mathematics for Applications, University of Oslo, P.O. Box 1053, Blindern, 0316 Oslo, Norway
E-mail: [email protected] b Masters EPITA, 14–16 rue Voltaire, 94276 Le Kremlin-Bicetre, France
E-mail: [email protected]
Received 26 March 2003; accepted 29 January 2004 Communicated by T. Sauer
In a recent paper by the first author, a simple proof was given of a result by Tutte on the validity of barycentric mappings, recast in terms of the injectivity of piecewise linear mappings over triangulations. In this note, we make a short extension to the proof to deal with arbitrary tilings. We also give a simple counterexample to show that convex combination mappings over tetrahedral meshes are not necessarily one-to-one. Keywords: triangulation, tiling, tetrahedral mesh, convex combination, discrete maximum principle, parameterization, planar embedding Mathematics subject classifications (2000): 05C10, 05C85, 65D17, 58E20
1.
Introduction
The idea of convex combination maps over triangulations has developed recently as a tool for parameterization of triangulations [4] and morphing of both triangulations and polygons [7,8]. Such maps are piecewise linear and generalize Tutte’s barycentric mappings; see [6,11]. It is important in practice to be able to guarantee the injectivity of the map and a sufficient condition is that the image of the triangulation boundary is convex. The first proof of this (for barycentric mappings) was given by Tutte [11] and takes an abstract graph-theoretic viewpoint. However, as pointed out recently by Colin de Verdière et al., Tutte’s theory is complicated even from the point of view of graph theory, and this motivated their simpler proof in [2]. Since then, an elementary proof which is independent of graph theory, was given in [6] for the case that the graph is a triangulation. The idea in [6] was to use the discrete maximum principle for convex combination functions in a similar way to the use of the continuous maximum principle for harmonic functions used
348
M.S. Floater, V. Pham-Trong / Convex combination maps
by Kneser [9] in his proof of the Radó–Kneser–Choquet theorem [1,9,10] for harmonic mappings. In this paper, we first show how the proof in [6] can be extended without too much difficulty to guarantee the validity of convex combination maps over arbitrary tilings (playing a similar role to the 3-connected graphs dealt with by Tutte). Note that these tilings include rectangular grids, which occur frequently in applications. We also give a simple counterexample to show that convex combination mappings over tetrahedral meshes are not necessarily one-to-one. 2.
Convex combination maps over tilings
By a face F we will understand the region enclosed by a convex polygon in the plane. Definition 2.1. Let T be a finite set of faces and let DT = tiling if
T ∈T
T . We will call T a
(i) the intersection of any pair of faces is
Data Loading...
