Acute triangulations of trapezoids

In this paper we discuss acute triangulations of trapezoids. It is known that every rectangle can be triangulated into eight acute triangles, and that this is best possible. In this paper we prove that all other trapezoids can be triangulated into at most seven acute triangles.     

Quasi-interpolation based on bivariate quadratic B-splines with multiple knots

Taking into account the results given in [1, 3, 4] on bivariate spline quasi-interpolation and in [5] on the effects of multiple knots, in this paper we consider local quadratic spline quasi-interpolants on criss-cross triangulations of a rectangular domain Ω, with possible multiple knots inside Ω and/or on the boundary ∂Ω. Such splines can be particularly useful in mechanics and engineering applications, since they can model constrained surfaces with different kind of smoothness in Ω. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Hamiltonian cycles in planar triangulations with no separating triangles

A classical theorem of Hassler Whitney asserts that any maximal planar graph with no separating triangles is Hamiltonian. In this paper, we examine the problem of generalizing Whitney's theorem by relaxing the requirement that the triangulation be a maximal planar graph (i.e., that its outer boundary be a triangle) while maintaining the hypothesis that the triangulation have no separating triangles. It is shown that the conclusion of Whitney's theorem still holds if the chords satisfy a certain sparse-ness condition and that a Hamiltonian cycle through a graph satisfying this condition can be found in linear time. Upper bounds on the shortness coefficient of triangulations without separating triangles are established. Several examples are given to show that the theorems presented here cannot be extended without strong additional hypotheses. In particular, a 1-tough, non-Hamiltonian triangulation with no separating triangles is presented.     

Adaptive spline–wavelet decompositions of two-dimensional numerical information flows

We consider triangulations of a domain that admit a local enlargement such that the obtained triangulation remains topologically correct. We discuss embedded Courant spaces for embedded triangulations and adaptive spline-wavelet decompositions of these spaces. The decomposition and reconstruction formulas for two-dimensional numerical flows are deduced. Bibliography: 5 titles.     

Asymptotic properties of some triangulations of the sphere

In this paper we analyse a method for triangulating the sphere originally proposed by Baumgardner and Frederickson in 1985. The method is essentially a refinement procedure for arbitrary spherical triangles that fit into a hemisphere. Refinement is carried out by dividing each triangle into four by introducing the midpoints of the edges as new vertices and connecting them in the usual ‘red’ way. We show that this process can be described by a sequence of piecewise smooth mappings from a reference triangle onto the spherical triangle. We then prove that the whole sequence of mappings is uniformly bi-Lipschitz and converges uniformly to a non-smooth parameterization of the spherical triangle, recovering the Baumgardner and Frederickson spherical barycentric coordinates. We also prove that the sequence of triangulations is quasi-uniform, that is, areas of triangles and lengths of the edges are roughly the same at each refinement level. Some numerical experiments confirm the theoretical results.     

On the number of hamiltonian cycles in triangulations with few separating triangles

In this article, we investigate the number of hamiltonian cycles in triangulations. We improve a lower bound of for the number of hamiltonian cycles in triangulations without separating triangles (4‐connected triangulations) by Hakimi, Schmeichel, and Thomassen to a linear lower bound and show that a linear lower bound even holds in the case of triangulations with one separating triangle. We confirm their conjecture about the number of hamiltonian cycles in triangulations without separating triangles for up to 25 vertices and give computational results and constructions for triangulations with a small number of hamiltonian cycles and 1–5 separating triangles.     

复杂外形设计中的C^1,C^2样条插值曲面

根据几种复杂外形设计的特点，木文构造了三角形域上Ｓ１２样条插值曲面，三角形域上的Ｃ２超限插值曲面，矩形参数域上Ｃ２超限插值曲面和任意四边形域上双三次Ｃ１，Ｃ２样条插值曲面，给出了一类有效的边界条件确定方法．同时，算法皆已应用到人体外形描述和飞机外形设计中．     

Multithread parallelization of Lepp-bisection algorithms

Longest edge (nested) algorithms for triangulation refinement in two dimensions are able to produce hierarchies of quality and nested irregular triangulations as needed both for adaptive finite element methods and for multigrid methods. They can be formulated in terms of the longest edge propagation path (Lepp) and terminal edge concepts, to refine the target triangles and some related neighbors. We discuss a parallel multithread algorithm, where every thread is in charge of refining a triangle t and its associated Lepp neighbors. The thread manages a changing Lepp(t) (ordered set of increasing triangles) both to find a last longest (terminal) edge and to refine the pair of triangles sharing this edge. The process is repeated until triangle t is destroyed. We discuss the algorithm, related synchronization issues, and the properties inherited from the serial algorithm. We present an empirical study that shows that a reasonably efficient parallel method with good scalability was obtained.     

2-isohedral triangulations

A triangulations is 2-isohedral iff there are exactly two orbits of triangles under the triangulation's symmetry group. 2-isohedral triangulations are classified using incidence symbols. This also determines the homeomeric types of 2-isohedral triangulation. There are 38 types. The proof is by aggregation into isohedral tilings and by reflection axis splitting.     

Simplicial grid refinement: on Freudenthal's algorithm and the optimal number of congruence classes

Summary. In the present paper we investigate Freudenthal's simplex refinement algorithm which can be considered to be the canonical generalization of Bank's well known red refinement strategy for triangles. Freudenthal's algorithm subdivides any given (n)-simplex into subsimplices, in such a way that recursive application results in a stable hierarchy of consistent triangulations. Our investigations concentrate in particular on the number of congruence classes generated by recursive refinements. After presentation of the method and the basic ideas behind it, we will show that Freudenthal's algorithm produces at most n!/2 congruence classes for any initial (n)-simplex, no matter how many subsequent refinements are performed. Moreover, we will show that this number is optimal in the sense that recursive application of any affine invariant refinement strategy with sons per element results in at least n!/2 congruence classes for almost all (n)-simplices. Received February 23, 1998/ Revised version received December 9, 1998 / Published online January 27, 2000     

The implementation of the finite-volume dynamical core in the community atmosphere model

A distributed memory message-passing parallel implementation of a finite-volume discretization of the primitive equations in the community atmosphere model (CAM) 3.0 is presented. These 3-D equations can be decoupled into a set of 2-D equations by the introduction of a floating vertical coordinate, resulting in considerable potential parallelism. Subsequent analysis of the data dependencies—in particular those arising from the polar singularity of the latitude-longitude coordinate system—suggests that two separate domain decompositions should be employed, each tailored for a different part of the model. The implementation requires that data be periodically redistributed between these two decompositions. Furthermore, data from nearest neighbors are kept in halo regions, which are updated between iterations. These data movements are optimized through one-sided communication primitives and multithreading. The resulting algorithm is shown to scale to very large machine configurations, even for relatively coarse resolutions.     

Lepp-bisection algorithms,applications and mathematical properties

Longest edge (nested) algorithms for triangulation refinement in two dimensions are able to produce hierarchies of quality and nested irregular triangulations as needed both for adaptive finite element methods and for multigrid methods for PDEs. In addition, right-triangle bintree triangulations are multiresolution algorithms used for terrain modeling and real time visualization of terrain applications. These algorithms are based on the properties of the consecutive bisection of a triangle by the median of the longest edge, and can be formulated in terms of the longest edge propagation path (Lepp) and terminal edge concepts, which implies the use of very local refinement operations over fully conforming meshes (where the intersection of pairs of neighbor triangles is either a common edge or a common vertex). In this paper we review the Lepp-bisection algorithms, their properties and applications. To the end we use recent simpler and stronger results on the complexity aspects of the bisection method and its geometrical properties. We discuss and analyze the computational costs of the algorithms. The generalization of the algorithms to 3-dimensions is also discussed. Applications of these methods are presented: for serial and parallel view dependent level of detail terrain rendering, and for the parallel refinement of tetrahedral meshes.     

Approximating the minimum weight steiner triangulation

We show that the length of the minimum weight Steiner triangulation (MWST) of a point set can be approximated within a constant factor by a triangulation algorithm based on quadtrees. InO(n logn) time we can compute a triangulation withO(n) new points, and no obtuse triangles, that approximates the MWST. We can also approximate the MWST with triangulations having no sharp angles. We generalize some of our results to higher-dimensional triangulation problems. No previous polynomial-time triangulation algorithm was known to approximate the MWST within a factor better thanO(logn).     

Generalized Park-Sheen Finite Elements for Adaptivity

The P1-nonconforming finite element method on simply connected Lipschitz domains partitioned into quadrilaterals was introduced by Park and Sheen in 2003. In order to apply mesh-adaptive refinement strategies, the concept is generalized to arbitrary triangulations into quadrilaterals and triangles of multiple connected Lipschitz domains. An explicit a priori analysis is given for second-order elliptic PDEs with inhomogeneous Dirichlet boundary conditions. (© 2012 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Acute Triangulations of Flat Mobius Strips

In this paper we investigate the acute triangulations of flat Mobius strips. We find out that we can always triangulate a flat Mobius strip with at most nine acute triangles, and sometimes (but not always) that many triangles are really needed.     

A Delaunay Refinement Algorithm for Quality 2-Dimensional Mesh Generation

We present a simple new algorithm for triangulating polygons and planar straightline graphs, It provides "shape" and "size" guarantees:

• All triangles have a bounded aspect ratio.

• The number of triangles is within a constant factor of optimal.

Such "quality" triangulations are desirable as meshes for the finite element method, in which the running time generally increases with the number of triangles, and where the convergence and stability may be hurt by very skinny triangles. The technique we use-successive refinement of a Delaunay triangulation-extends a mesh generation technique of Chew by allowing triangles of varying sizes. Compared with previous quadtree-based algorithms for quality mesh generation, the Delaunay refinement approach is much simpler and generally produces meshes with fewer triangles. We also discuss an implementation of the algorithm and evaluate its performance on a variety of inputs.     

Generalized delaunay triangulation for planar graphs

We introduce the notion of generalized Delaunay triangulation of a planar straight-line graphG=(V, E) in the Euclidean plane and present some characterizations of the triangulation. It is shown that the generalized Delaunay triangulation has the property that the minimum angle of the triangles in the triangulation is maximum among all possible triangulations of the graph. A general algorithm that runs inO(|V|²) time for computing the generalized Delaunay triangulation is presented. When the underlying graph is a simple polygon, a divide-and-conquer algorithm based on the polygon cutting theorem of Chazelle is given that runs inO(|V| log |V|) time.Supported in part by the National Science Foundation under Grants DCR 8420814 and ECS 8340031.     

Frieze patterns for punctured discs

We construct frieze patterns of type D _N with entries which are numbers of matchings between vertices and triangles of corresponding triangulations of a punctured disc. For triangulations corresponding to orientations of the Dynkin diagram of type D _N , we show that the numbers in the pattern can be interpreted as specialisations of cluster variables in the corresponding Fomin-Zelevinsky cluster algebra. This is generalised to arbitrary triangulations in an appendix by Hugh Thomas.     

Triangulations intersect nicely

We show that there is a matching between the edges of any two triangulations of a planar point set such that an edge of one triangulation is matched either to the identical edge in the other triangulation or to an edge that crosses it. This theorem also holds for the triangles of the triangulations and in general independence systems. As an application, we give some lower bounds for the minimum-weight triangulation which can be computed in polynomial time by matching and network-flow techniques. We exhibit an easy-to-recognize class of point sets for which the minimum-weight triangulation coincides with the greedy triangulation.     

An hp‐adaptive refinement strategy for hypersingular operators on surfaces

An adaptive refinement strategy for the hp‐version of the boundary element method with hypersingular operators on surfaces is presented. The error indicators are based on local projections provided by two‐level decompositions of ansatz spaces with additional bubble functions. Assuming a saturation property and locally quasi‐uniform meshes, efficiency and reliability of the resulting error estimator is proved. A second error estimator based on mesh refinement and overlapping decompositions that better fulfills the saturation property is presented. The performance of the algorithm and the estimators is demonstrated for a model problem. © 2002 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 18: 396–419, 2002; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/num.10011