Properties of triangulations obtained by the longest-edge bisection

The Longest-Edge (LE) bisection of a triangle is obtained by joining the midpoint of its longest edge with the opposite vertex. Here two properties of the longest-edge bisection scheme for triangles are proved. For any triangle, the number of distinct triangles (up to similarity) generated by longest-edge bisection is finite. In addition, if LE-bisection is iteratively applied to an initial triangle, then minimum angle of the resulting triangles is greater or equal than a half of the minimum angle of the initial angle. The novelty of the proofs is the use of an hyperbolic metric in a shape space for triangles.     

Towards a more efficient dynamic mesh adaptation methodology for continuum discretization in complex engineering problems

A novel and efficient method of adaptive mesh generation, for dynamically adaptive unstructured grids, is proposed. A locally refined triangulation is constructed on a coarse background mesh, subdividing each triangle in the refinement region R into four congruent sub-triangles iteratively, by connecting edge midpoints, until triangles of a prescribed lengthscale are obtained. The unavoidable propagation outside the refinement region R is restricted to a single triangle in the coarse background mesh. The triangles, in the immediate vicinity of region R, are broken down using the concept of iterated function systems, widely used in fractal modeling, by recursive generation of sub-triangles with a gradation towards the region R triangles. A quantitative assessment of the present algorithm proves its superiority over other comparable models reported in the literature. The time cost of the algorithm is linear, and the method can be easily extended to three dimensions.     

W-加密三角剖分下二元五次超样条函数空间的局部Lagrange插值

本文选取二元五次C2超样条函数空间作为插值空间,考虑局部Lagrange插值.首先对三角剖分△进行着色,通过Wang-加密三角剖分对原剖分△细分大约一半的三角形.然后通过在内边增加一些另外的光滑条件,使得样条函数在某些边上达到更高阶的光滑.最后在△的加密三角剖分内选择Lagrange插值点.结果表明相应的插值基函数具有...     

On the non-degeneracy property of the longest-edge trisection of triangles

The longest-edge (LE) trisection of a triangle t is obtained by joining the two equally spaced points of the longest-edge of t with the opposite vertex. In this paper we prove that for any given triangle t with smallest interior angle τ>0, if the minimum interior angle of the three triangles obtained by the LE-trisection of t into three new triangles is denoted by τ₁, then τ₁?τ/c₁, where . Moreover, we show empirical evidence on the non-degeneracy property of the triangular meshes obtained by iterative application of the LE-trisection of triangles. If τ_n denotes the minimum angle of the triangles obtained after n iterative applications of the LE-trisection, then τ_n>τ/c where c is a positive constant independent of n. An experimental estimate of c≈6.7052025350 is provided.     

Hamilton cycles in plane triangulations

We extend Whitney's Theorem that every plane triangulation without separating triangles is hamiltonian by allowing some separating triangles. More precisely, we define a decomposition of a plane triangulation G into 4‐connected ‘pieces,’ and show that if each piece shares a triangle with at most three other pieces then G is hamiltonian. We provide an example to show that our hypothesis that each piece shares a triangle with at most three other pieces' cannot be weakened to ‘four other pieces.’ As part of our proof, we also obtain new results on Tutte cycles through specified vertices in planar graphs. © 2002 Wiley Periodicals, Inc. J Graph Theory 41: 138–150, 2002     

The 4-triangles longest-side partition of triangles and linear refinement algorithms

In this paper we study geometrical properties of the iterative 4-triangles longest-side partition of triangles (and of a 3-triangles partition), as well as practical algorithms based on these partitions, used both directly for the triangulation refinement problem, and as a basis for point insertion strategies in Delaunay refinement algorithms. The 4-triangles partition is obtained by joining the midpoint of the longest side with the opposite vertex and the midpoints of the two remaining sides. By means of simple geometrical arguments we show that the iterative partition of obtuse triangles systematically improves the triangles (while they remain obtuse) in the following sense: the sequence of smallest angles monotonically increases while the sequence of largest angles monotonically decreases in an amount (at least) equal to the smallest angle of each iteration. This allows us to improve the known bound on the smallest angle (without making use of previous results), and to obtain a better a priori bound on the number of similarly distinct triangles, as a function of the geometry of the initial triangle. Numerical evidence, showing that the practical behavior of the 4-triangles partition is in complete agreement with this theory, is included. A 4-triangles refinement algorithm is also discussed and illustrated. Furthermore, we show that the time cost of the algorithm is linear independently of the size of the triangulation.

     

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.     

Optimality of the Delaunay triangulation in ℝ d

In this paper we present new optimality results for the Delaunay triangulation of a set of points in ℝ ^d . These new results are true in all dimensionsd. In particular, we define a power function for a triangulation and show that the Delaunay triangulation minimizes the power function over all triangulations of a point set. We use this result to show that (a) the maximum min-containment radius (the radius of the smallest sphere containing the simplex) of the Delaunay triangulation of a point set in ℝ ^d is less than or equal to the maximum min-containment radius of any other triangulation of the point set, (b) the union of circumballs of triangles incident on an interior point in the Delaunay triangulation of a point set lies inside the union of the circumballs of triangles incident on the same point in any other triangulation of the point set, and (c) the weighted sum of squares of the edge lengths is the smallest for Delaunay triangulation, where the weight is the sum of volumes of the triangles incident on the edge. In addition we show that if a triangulation consists of only self-centered triangles (a simplex whose circumcenter falls inside the simplex), then it is the Delaunay triangulation.     

Direct sums of finitary permutation groups

The interpolation problem under consideration is connected with the finite element method in ?³. In most cases, when finite elements are constructed by means of the partition of a given domain in ?² into triangles and interpolation of the Hermite or Birkhoff type, the sine of the smallest angle of the triangle appears in the denominators of the error estimates for the derivatives. In the case of ? ^m (m ≥ 3), the ratio of the radius of the inscribed sphere to the diameter of the simplex is used as an analog of this characteristic. This makes it necessary to impose constraints on the triangulation of the domain. The recent investigations by a number of authors reveal that, in the case of triangles, the smallest angle in the error estimates for some interpolation processes can be replaced by the middle or the greatest one, which makes it possible to weaken the triangulation requirements. There are fewer works of this kind for m ≥ 3, and the error estimates are given there in terms of other characteristics of the simplex. In this paper, methods are suggested for constructing an interpolation third-degree polynomial on a simplex in ?³. These methods allow one to obtain estimates in terms of a new characteristic of a rather simple form and weaken the triangulation requirements.     

Piecewise linear wavelets on sierpinski gasket type fractals

Let SG denote the Sierpinski gasket with Hausdorff measure μ of dimensionlog 3/log 2, let PL_k denote the continuous piecewise linear functions with respect to the usual triangulation of SG into 3^k triangles, and let W_k denote the orthogonal complement of PL_k−1 in PL_k. We construct a basis for each W_k, so that the entire collection is a frame for L²(dμ). This wavelet basis is obtained from three wavelet generators by scaling, translation and rotation, and the wavelets are supported either by one corner triangle or a pair of adjacent triangles in the triangulation of level k − 1. Analogous bases are constructed in the von Koch curve, the hexagasket, and the n-dimensional analog of SG.     

Hot spots conjecture for a class of acute triangles

We show that the hot spots conjecture of J. Rauch holds for acute triangles if one of the angles is not larger than \(\pi /6\). More precisely, we show that the second Neumann eigenfunction on those acute triangles has no maximum or minimum inside the domain. We first simplify the problem by showing that absence of critical points on two sides implies no critical points inside a triangle. This result applies to any acute triangle and might help prove the conjecture for arbitrary acute triangles. Then we show that there are no critical points on two sides assuming one small angle. We also establish simplicity for the smallest positive Neumann eigenvalue for all non-equilateral acute triangles. This result was already known for obtuse triangles, and it fails for the equilateral case.     

On the adjacencies of triangular meshes based on skeleton-regular partitions

For any 2D triangulation τ, the 1-skeleton mesh of τ is the wireframe mesh defined by the edges of τ, while that for any 3D triangulation τ, the 1-skeleton and the 2-skeleton meshes, respectively, correspond to the wireframe mesh formed by the edges of τ and the “surface” mesh defined by the triangular faces of τ. A skeleton-regular partition of a triangle or a tetrahedra, is a partition that globally applied over each element of a conforming mesh (where the intersection of adjacent elements is a vertex or a common face, or a common edge) produce both a refined conforming mesh and refined and conforming skeleton meshes. Such a partition divides all the edges (and all the faces) of an individual element in the same number of edges (faces). We prove that sequences of meshes constructed by applying a skeleton-regular partition over each element of the preceding mesh have an associated set of difference equations which relate the number of elements, faces, edges and vertices of the nth and (n−1)th meshes. By using these constitutive difference equations we prove that asymptotically the average number of adjacencies over these meshes (number of triangles by node and number of tetrahedra by vertex) is constant when n goes to infinity. We relate these results with the non-degeneracy properties of longest-edge based partitions in 2D and include empirical results which support the conjecture that analogous results hold in 3D.     

A Pedestrian Approach to Ray Shooting: Shoot a Ray, Take a Walk

We propose a very simple ray-shooting algorithm, whose only data structure is a triangulation. The query algorithm, after locating the triangle containing the origin of the ray, walks along the ray, advancing from one triangle to a neighboring one until the polygon boundary is reached. The key result of the paper is a Steiner triangulation of a simple polygon with the property that a ray can intersect at most O(log n) triangles before reaching the polygon boundary. We are able to compute such a triangulation in linear sequential time, or in O(log n) parallel time using O(n/log n) processors. This gives a simple, yet optimal, ray-shooting algorithm for a simple polygon. Using a well-known technique, we can extend our triangulation procedure to a multiconnected polygon with k components and n vertices, so that a ray intersects at most O(√k log n) triangles.     

Adaptive simplification of huge sets of terrain grid data for geosciences applications

We propose and discuss a new Lepp-surface method able to produce a small triangular approximation of huge sets of terrain grid data by using a two-goal strategy that assures both small approximation error and well-shaped 3D triangles. This is a refinement method which starts with a coarse initial triangulation of the input data, and incrementally selects and adds data points into the mesh as follows: for the edge e having the highest error in the mesh, one or two points close to (one or two) terminal edges associated with e are inserted in the mesh. The edge error is computed by adding the triangle approximation errors of the two triangles that share e, while each L₂-norm triangle error is computed by using a curvature tensor (a good approximation of the surface) at a representative point associated with both triangles. The method produces triangular approximations that capture well the relevant features of the terrain surface by naturally producing well-shaped triangles. We compare our method with a pure L₂-norm optimization method.     

On Constants for Cuttings in the Plane

A theorem of Chazelle and Friedman with numerous applications in combinatorial and computational geometry asserts that for any set L of n lines in the plane and for any parameter r>1 there exists a subdivision of the plane into at most Cr ² (possibly unbounded) triangles, C a constant, such that the interior of each triangle is intersected by at most n/r lines of L . (Such a subdivision is called a (1/r) -cutting for L .) We give upper and lower bounds on the constant C . We also consider the canonical triangulation of the arrangement of a random sample of r lines from L . Although this typically is not a (1/r) -cutting, the expectation of the k th degree average of the number of lines intersecting a triangle is O(n/r) for any fixed k . We estimate the constant of proportionality in this result. Received October 1, 1996, and in revised form September 25, 1997.     

Besicovitch triangles cover unit arcs

A long standing conjecture is that the Besicovitch triangle, i.e., an equilateral triangle with side is a worm-cover. We will show that indeed there exists a class of isosceles triangles, that includes the above equilateral triangle, where each triangle from the class is a worm-cover. These triangles are defined so that the shortest symmetric z-arc stretched from side to side and touching the base would have length one.      

Algorithms for optimal area triangulations of a convex polygon

Given a convex polygon with n vertices in the plane, we are interested in triangulations of its interior, i.e., maximal sets of non-intersecting diagonals that subdivide the interior of the polygon into triangles. The MaxMin area triangulation is the triangulation of the polygon that maximizes the area of the smallest triangle in the triangulation. Similarly, the MinMax area triangulation is the triangulation that minimizes the area of the largest area triangle in the triangulation. We present algorithms that construct MaxMin and MinMax area triangulations of a convex polygon in O(n²logn) time and O(n²) space. The algorithms use dynamic programming and a number of geometric properties that are established within the paper.     

Periodic reflecting paths in right triangles

A reflecting path in a Jordan curve has the ready physical analogies of a billiards ball bouncing off the cushions of a custom billiards table and of a laser beam reflecting off the mirrored boundary of a thin cavity. What does the curve tell us about the possible reflecting paths? Two types of reflecting paths are of perennial interest — periodic paths and dense paths. In 1927, G. D. Birkhoff applied a theorem of Poincaré to the billiards ball analogy to show that for anyk>1 and anyw<k/2, with (w, k)=1, a smooth convex curve admits at least two periodic reflecting paths ofk reflections per cycle and winding numberw. Unfortunately Birkhoff's proof does not extent to polygons, nor has any other method been found to yield such sweeping results. Various techniques have produced results for polygons-with-angles-commensurable-with-π and for acute triangles. It was not clear whether an arbitrary right triangle admitted periodic paths. Two simple constructions demonstrate the existence of periodic reflecting paths in right triangles. This paper explores these two constructions, focusing on the simplest result: Let β represent the smallest interior angle of some right triangle, and letN=[π/2β]?1. Then each point interior to the shorter leg of the right triangle lies on a unique reflecting path of (4k+2) reflections per cycle for allk=1,2,...,N?1; and each point interior to some subsegment of the shorter leg lies on a unique reflecting path of 4N+2 reflections per cycle.     

Multiple-scale decomposition for the Zlamal approximation

For the Zlamal approximation (a piecewise-polynomial continuous approximation of degree at most two), it is proved that the space of approximating functions obtained by subdividing a triangulation contains the space corresponding to the given triangulation. Formulas for the multiple-scale decomposition (that is, the decomposition of old basis functions in the new ones) are explicitly written in the case of placing one additional vertex on one edge of the initial triangulation. The cases of placing a vertex on a boundary or an interior edge are considered. The obtained formulas can also be used when several vertices are added to sufficiently distant triangles, because the operation under consideration and its influence on the coefficients in the decomposition of the approximating function in the standard Zlamal basis are local. The local bases of the additional terms W in the decomposition of the new space of approximating functions into the direct sum of the old space and W are specified (in particular, in the cases of placing a new vertex on a boundary or an interior edge). For these bases, decomposition formulas and reconstructions of the wavelet transform are explicitly written. All of the formulas were tested by using the MuPAD 2.5.3 computer algebra system running under Linux.     

A model to simplify 2D triangle meshes with irregular shapes

We present a 2D triangle mesh simplification model which is able to produce high quality approximations of any original planar mesh, regardless of the shape of the original mesh. This method consists of two phases: a self-organizing algorithm and a triangulation algorithm. The self-organizing algorithm is an unsupervised incremental clustering algorithm which provides us a set of nodes representing the best approximation of the original mesh. The triangulation algorithm reconstructs the simplified mesh from the planar points obtained by the self-organizing training process. Some examples are detailed with the purpose of demonstrating the ability of the model to perform the task of simplifying an original mesh with irregular shape.