Compatible triangulations and point partitions by series-triangular graphs

We introduce series-triangular graph embeddings and show how to partition point sets with them. This result is then used to prove an upper bound on the number of Steiner points needed to obtain compatible triangulations of point sets. The problem is generalized to finding compatible triangulations for more than two point sets and we show that such triangulations can be constructed with only a linear number of Steiner points added to each point set. Moreover, the compatible triangulations constructed by these methods are regular triangulations.     

Measures for comparing discrete models of single-valued surfaces

The problem of comparing surfaces unambiguously projected on a plane and represented by clouds of points with three-dimensional coordinates is considered. This problem can be reduced to the problem of comparing functions of two variables determined on different finite sets of points, i.e., on nodes of different grids. A new measure for comparing such surfaces and a new numerically efficient algorithm for calculating them are proposed for the general case in which both grids are unstructured and can have different densities. The linear (with respect to the number of points in two grids) estimate of the complexity of the algorithm for calculating the introduced measure, based on two Delaunay triangulations of the initial sets of points, is proved.     

Delaunay Triangulation of Manifolds

We present an algorithm for producing Delaunay triangulations of manifolds. The algorithm can accommodate abstract manifolds that are not presented as submanifolds of Euclidean space. Given a set of sample points and an atlas on a compact manifold, a manifold Delaunay complex is produced for a perturbed point set provided the transition functions are bi-Lipschitz with a constant close to 1, and the original sample points meet a local density requirement; no smoothness assumptions are required. If the transition functions are smooth, the output is a triangulation of the manifold. The output complex is naturally endowed with a piecewise-flat metric which, when the original manifold is Riemannian, is a close approximation of the original Riemannian metric. In this case the output complex is also a Delaunay triangulation of its vertices with respect to this piecewise-flat metric.     

Bregman Voronoi Diagrams

The Voronoi diagram of a finite set of objects is a fundamental geometric structure that subdivides the embedding space into regions, each region consisting of the points that are closer to a given object than to the others. We may define various variants of Voronoi diagrams depending on the class of objects, the distance function and the embedding space. In this paper, we investigate a framework for defining and building Voronoi diagrams for a broad class of distance functions called Bregman divergences. Bregman divergences include not only the traditional (squared) Euclidean distance but also various divergence measures based on entropic functions. Accordingly, Bregman Voronoi diagrams allow one to define information-theoretic Voronoi diagrams in statistical parametric spaces based on the relative entropy of distributions. We define several types of Bregman diagrams, establish correspondences between those diagrams (using the Legendre transformation), and show how to compute them efficiently. We also introduce extensions of these diagrams, e.g., k-order and k-bag Bregman Voronoi diagrams, and introduce Bregman triangulations of a set of points and their connection with Bregman Voronoi diagrams. We show that these triangulations capture many of the properties of the celebrated Delaunay triangulation.     

An efficient algorithm for enumeration of triangulations

We consider the problem of enumerating triangulations of n points in the plane in general position. We introduce a tree of triangulations and present an algorithm for enumerating triangulations in O(loglogn) time per triangulation. It improves the previous bound by almost linear factor.     

Exploiting structure in piecewise-linear homotopy algorithms for solving equations

We consider the recent algorithms for computing fixed points or zeros of continuous functions fromR ⁿ to itself that are based on tracing piecewise-linear paths in triangulations. We investigate the possible savings that arise when these fixed-point algorithms with their usual triangulations are applied to computing zeros of functionsf with special structure:f is either piecewise-linear in certain variables, separable, or has Jacobian with small bandwidth. Each of these structures leads to a property we call modularity; the algorithmic path within a simplex can be continued into an adjacent simplex without a function evaluation or linear programming pivot. Modularity also arises without any special structure onf from the linearity of the function that is deformed tof. In the case thatf is separable we show that the path generated by Kojima's algorithm with the homotopyH ² coincides with the path generated by the standard restart algorithm of Merrill when the usual triangulations are employed. The extra function evaluations and linear programming steps required by the standard algorithm can be avoided by exploiting modularity.This research was performed while the author was visiting the Mathematics Research Center, University of Wisconsin-Madison, and was sponsored by the United States Army under Contract No. DAAG-29-75-C-0024 and by the National Science Foundation under Grant No. ENG76-08749.     

Data Dependent Triangulations for Piecewise Linear Interpolation

Given a set of data points in R² and corresponding data values,it is clear that the quality of a piecewise linear interpolationover triangles depends on the specific triangulation of thedata points. While conventional triangulation methods dependonly on the distribution of the data points in R² in this paperwe suggest that the triangulation should depend on the datavalues as well. Several data dependent criteria for definingthe triangulation are discussed and efficient algorithms forcomputing these triangulations are presented. It is shown fora variety of test cases that data dependent triangulations canimprove significantly the quality of approximation and thatlong and thin triangles, which are traditionally avoided, aresometimes very suitable.     

Generating realistic terrains with higher-order Delaunay triangulations

For hydrologic applications, terrain models should have few local minima, and drainage lines should coincide with edges. We show that triangulating a set of points with elevations such that the number of local minima of the resulting terrain is minimized is NP-hard for degenerate point sets. The same result applies when there are no degeneracies for higher-order Delaunay triangulations. Two heuristics are presented to reduce the number of local minima for higher-order Delaunay triangulations, which start out with the Delaunay triangulation. We give efficient algorithms for their implementation, and test on real-world data how well they perform. We also study another desirable drainage characteristic, few valley components, and how to obtain it for higher-order Delaunay triangulations. This gives rise to a third heuristic. Tables and visualizations show how the heuristics perform for the drainage characteristics on real-world data.     

Splines on Triangulations with Hanging Vertices

Polynomial spline spaces defined on triangulations with hanging vertices are studied. In addition to dimension formulae, explicit basis functions are constructed, and their supports and stability are discussed. The approximation power of the spaces is also treated.     

Nonconforming P1 elements on distorted triangulations: Lower bounds for the discrete energy norm error

Compared to conforming P1 finite elements, nonconforming P1 finite element discretizations are thought to be less sensitive to the appearance of distorted triangulations. E.g., optimal-order discrete H¹ norm best approximation error estimates for H² functions hold for arbitrary triangulations. However, the constants in similar estimates for the error of the Galerkin projection for second-order elliptic problems show a dependence on the maximum angle of all triangles in the triangulation. We demonstrate on an example of a special family of distorted triangulations that this dependence is essential, and due to the deterioration of the consistency error. We also provide examples of sequences of triangulations such that the nonconforming P1 Galerkin projections for a Poisson problem with polynomial solution do not converge or converge at arbitrarily low speed. The results complement analogous findings for conforming P1 finite elements.     

An improvement of fixed point algorithms by using a good triangulation

We consider measures for triangulations ofR ⁿ. A new measure is introduced based on the ratio of the length of the sides and the content of the subsimplices of the triangulation. In a subclass of triangulations, which is appropriate for computing fixed points using simplicial subdivisions, the optimal one according to this measure is calculated and some of its properties are given. It is proved that for the average directional density this triangulation is optimal (within the subclass) asn goes to infinity. Furthermore, we compare the measures of the optimal triangulation with those of other triangulations. We also propose a new triangulation of the affine hull of the unit simplex. Finally, we report some computational experience that confirms the theoretical results.     

Three-pencil lattices on triangulations

In this paper, three-pencil lattices on triangulations are studied. The explicit representation of a lattice, based upon barycentric coordinates, enables us to construct lattice points in a simple and numerically stable way. Further, this representation carries over to triangulations in a natural way. The construction is based upon group action of S ₃ on triangle vertices, and it is shown that the number of degrees of freedom is equal to the number of vertices of the triangulation.      

Piecewise Linear Bases and Besov Spaces on Fractal Sets

For a class of closed sets F R ⁿ admitting a regular sequence of triangulations or generalized triangulations, the analogues on F of the Faber—Schauder and Franklin bases are discussed. The characterizations of the Besov spaces on F in the terms of coefficients of functions with respect to these bases are proved. As a consequence, analogous characterizations of the Besov spaces on some fractal domains (including the Sierpinski gasket and the von Koch curve) by coefficients of functions with respect to the wavelet bases constructed in [26] are obtained.     

The fibres of the Scott map on polygon tilings are the flip equivalence classes

Monatshefte für Mathematik - We define a map from tilings of surfaces with marked points to strand diagrams, generalising Scott’s construction for the case of triangulations of polygons....     

New bijective links on planar maps via orientations

This article presents new bijections on planar maps. At first a bijection is established between bipolar orientations on planar maps and specific “transversal structures” on triangulations of the 4-gon with no separating 3-cycle, which are called irreducible triangulations. This bijection specializes to a bijection between rooted non-separable maps and rooted irreducible triangulations. This yields in turn a bijection between rooted loopless maps and rooted triangulations, based on the observation that loopless maps and triangulations are decomposed in a similar way into components that are respectively non-separable maps and irreducible triangulations. This gives another bijective proof (after Wormald’s construction published in 1980) of the fact that rooted loopless maps with n edges are equinumerous to rooted triangulations with n inner vertices.     

Principal Component Analysis of Two-Dimensional Functional Data

This article presents and compares two approaches of principal component (PC) analysis for two-dimensional functional data on a possibly irregular domain. The first approach applies the singular value decomposition of the data matrix obtained from a fine discretization of the two-dimensional functions. When the functions are only observed at discrete points that are possibly sparse and may differ from function to function, this approach incorporates an initial smoothing step prior to the singular value decomposition. The second approach employs a mixed effects model that specifies the PC functions as bivariate splines on triangulations and the PC scores as random effects. We apply the thin-plate penalty for regularizing the function estimation and develop an effective expectation–maximization algorithm for calculating the penalized likelihood estimates of the parameters. The mixed effects model-based approach integrates scatterplot smoothing and functional PC analysis in a unified framework and is shown in a simulation study to be more efficient than the two-step approach that separately performs smoothing and PC analysis. The proposed methods are applied to analyze the temperature variation in Texas using 100 years of temperature data recorded by Texas weather stations. Supplementary materials for this article are available online.     

Off-centers: A new type of Steiner points for computing size-optimal quality-guaranteed Delaunay triangulations

We introduce a new type of Steiner points, called off-centers, as an alternative to circumcenters, to improve the quality of Delaunay triangulations in two dimensions. We propose a new Delaunay refinement algorithm based on iterative insertion of off-centers. We show that this new algorithm has the same quality and size optimality guarantees of the best known refinement algorithms. In practice, however, the new algorithm inserts fewer Steiner points, runs faster, and generates smaller triangulations than the best previous algorithms. Performance improvements are significant especially when user-specified minimum angle is large, e.g., when the smallest angle in the output triangulation is 30°, the number of Steiner points is reduced by about 40%, while the mesh size is down by about 30%. As a result of its shown benefits, the algorithm described here has already replaced the well-known circumcenter insertion algorithm of Ruppert and has been the default quality triangulation method in the popular meshing software Triangle.¹     

New Cartesian grid methods for interface problems using the finite element formulation

Summary New finite element methods based on Cartesian triangulations are presented for two dimensional elliptic interface problems involving discontinuities in the coefficients. The triangulations in these methods do not need to fit the interfaces. The basis functions in these methods are constructed to satisfy the interface jump conditions either exactly or approximately. Both non-conforming and conforming finite element spaces are considered. Corresponding interpolation functions are proved to be second order accurate in the maximum norm. The conforming finite element method has been shown to be convergent. With Cartesian triangulations, these new methods can be used as finite difference methods. Numerical examples are provided to support the methods and the theoretical analysis. Mathematics Subject Classification (2000):65L10, 65L60, 65L70In this research, Zhilin Li is supported in part by USA ARO grants, 39676-MA and 43751-MA, USA NSF grants DMS-0073403 and DMS-0201094; USA North Carolina State University FR&PD grant; Tao Lin is supported in part a USA NSF grant DMS-97-04621. Special thanks to Thomas Hou for his participation and contribution to this project. We are also grateful to R. LeVeque, K. Bube, and T. Chan for useful discussions.     

Harmonic deformation of Delaunay triangulations

We construct harmonic functions on random graphs given by Delaunay triangulations of ergodic point processes as the limit of the zero-temperature harness process.