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.     

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.     

Computational Complexity of the Vertex Cover Problem in the Class of Planar Triangulations

We study the computational complexity of the vertex cover problem in the class of planar graphs (planar triangulations) admitting a plane representation whose faces are triangles. It is shown that the problem is strongly NP-hard in the class of 4-connected planar triangulations in which the degrees of vertices are of order O(log n), where n is the number of vertices, and in the class of plane 4-connected Delaunay triangulations based on the Minkowski triangular distance. A pair of vertices in such a triangulation is adjacent if and only if there is an equilateral triangle ?(p, λ) with p ∈ R² and λ > 0 whose interior does not contain triangulation vertices and whose boundary contains this pair of vertices and only it, where ?(p, λ) = p + λ? = {x ∈ R²: x = p + λa, a ∈ ?}; here ? is the equilateral triangle with unit sides such that its barycenter is the origin and one of the vertices belongs to the negative y-axis. Keywords: computational complexity, Delaunay triangulation, Delaunay TD-triangulation.     

A Linear Bound on the Complexity of the Delaunay Triangulation of Points on Polyhedral Surfaces

Delaunay triangulations and Voronoi diagrams have found numerous applications in surface modeling, surface mesh generation, deformable surface modeling and surface reconstruction. Many algorithms in these applications begin by constructing the three-dimensional Delaunay triangulation of a finite set of points scattered over a surface. Their running-time therefore depends on the complexity of the Delaunay triangulation of such point sets. Although the complexity of the Delaunay triangulation of points in R³ may be quadratic in the worst case, we show in this paper that it is only linear when the points are distributed on a fixed set of well-sampled facets of R³ (e.g. the planar polygons in a polyhedron). Our bound is deterministic and the constants are explicitly given.     

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).     

Uniform Infinite Planar Triangulation and Related Time-Reversed Critical Branching Process

We consider the uniform infinite planar triangulation, which is defined as the weak limit of the uniform distributions on finite triangulations with N triangles as N → ∞. Take the ball of radius R in an infinite triangulation. One of the components of its boundary separates this ball from the infinite part of the triangulation, and we denote its length by ℓ(R). The main question we study is the asymptotic behavior of the sequence ℓ(R), R = 1, 2,..., called the triangulation profile. First, we prove that the ratio ℓ(R)/R² converges to a nondegenerate random variable. Second, we establish a connection between the triangulation profile and a certain time-reversed critical branching process. Finally, we show that there exists a contour of length linear in R that lies outside of the R-ball and separates this ball from the infinite part of the triangulation. Bibliography: 8 titles. __________ Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 307, 2004, pp. 141–174.     

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.     

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.     

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.     

The Number of Geometric Bistellar Neighbors of a Triangulation

The theory of secondary and fiber polytopes implies that regular (also called convex or coherent) triangulations of configurations with n points in R ^d have at least n-d-1 geometric bistellar neighbors. Here we prove that, in fact, all triangulations of n points in R ² have at least n-3 geometric bistellar neighbors. In a similar way, we show that for three-dimensional point configurations, in convex position and with no three points collinear, all triangulations have at least n-4 geometric bistellar flips. In contrast, we exhibit three-dimensional point configurations, with a single interior point, having deficiency on the number of geometric bistellar flips. A lifting technique allows us to obtain a triangulation of a simplicial convex 4-polytope with less than n-5 neighbors. We also construct a family of point configurations in R ³ with arbitrarily large flip deficiency. Received November 25, 1996, and in revised form March 10, 1997.     

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

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

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.¹     

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.     

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.     

Degree-regular triangulations of torus and Klein bottle

A triangulation of a connected closed surface is called weakly regular if the action of its automorphism group on its vertices is transitive. A triangulation of a connected closed surface is called degree-regular if each of its vertices have the same degree. Clearly, a weakly regular triangulation is degree-regular. In [8], Lutz has classified all the weakly regular triangulations on at most 15 vertices. In [5], Datta and Nilakantan have classified all the degree-regular triangulations of closed surfaces on at most 11 vertices. In this article, we have proved that any degree-regular triangulation of the torus is weakly regular. We have shown that there exists ann-vertex degree-regular triangulation of the Klein bottle if and only if n is a composite number ≥ 9. We have constructed two distinctn-vertex weakly regular triangulations of the torus for eachn ≥ 12 and a (4m + 2)-vertex weakly regular triangulation of the Klein bottle for eachm ≥ 2. For 12 ≤n ≤ 15, we have classified all then-vertex degree-regular triangulations of the torus and the Klein bottle. There are exactly 19 such triangulations, 12 of which are triangulations of the torus and remaining 7 are triangulations of the Klein bottle. Among the last 7, only one is weakly regular.     

A research note on design of fair surfaces over irregular domains using data-dependent triangulation

Design of fair surfaces over irregular domain is a fundamental problem in computer aided geometric design (CAGD), and has applications in engineering sciences (i.e. aircraft science, automobile science and ship science etc.). In design of fair surfaces over irregular domain defined over scattered data it was widely accepted till recently that one should use Delaunay triangulation because of its global optimum property. However, in recent times it has been shown that for continuous piecewise polynomial parametric surfaces improvements in the quality of fit can be achieved if the triangulation pattern is made dependent upon some topological property of the data set or is simply data dependent. The smoothness and fairness of surface’s planar cuts is important because not only it ensures favorable hydrodynamic drag, but also helps in reducing manhours during the production of the surface. In this paper we discuss a method for construction of C¹ piecewise polynomial parametric fair surfaces which interpolate prescribed R³${\mathfrak{R}}^3$ scattered data using spaces of parametric splines defined on R³${\mathfrak{R}}^3$ triangulation. We show that our method is more specific to the cases when the projection on 2-D plane may consist of triangles of zero area. The proposed method is fast, numerically stable and robust, and computationally inexpensive. In the present work numerical examples dealing with surfaces approximated on standard curved plates, and ship hull surface have been presented.     

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.     

Approximating Minimum-Weight Triangulations in Three Dimensions

Let S be a set of noncrossing triangular obstacles in R ³ with convex hull H . A triangulation T of H is compatible with S if every triangle of S is the union of a subset of the faces of T. The weight of T is the sum of the areas of the triangles of T. We give a polynomial-time algorithm that computes a triangulation compatible with S whose weight is at most a constant times the weight of any compatible triangulation. One motivation for studying minimum-weight triangulations is a connection with ray shooting. A particularly simple way to answer a ray-shooting query (``Report the first obstacle hit by a query ray') is to walk through a triangulation along the ray, stopping at the first obstacle. Under a reasonably natural distribution of query rays, the average cost of a ray-shooting query is proportional to triangulation weight. A similar connection exists for line-stabbing queries (``Report all obstacles hit by a query line'). Received February 3, 1997, and in revised form August 21, 1998.