A Large Subgraph of the Minimum Weight Triangulation

We present an O(n ⁴ )-time and O(n ² )-space algorithm that computes a subgraph of the minimum weight triangulation (MWT) of a general point set. The algorithm works by finding a collection of edges guaranteed to be in any locally minimal triangulation. We call this subgraph the LMT-skeleton. We also give a variant called the modified LMT-skeleton that is both a more complete subgraph of the MWT and is faster to compute requiring only O(n ² ) time and O(n) space in the expected case for uniform distributions. Several experimental implementations of both approaches have shown that for moderate-sized point sets (up to 350 points^1) the skeletons are connected, enabling an efficient completion of the exact MWT. We are thus able to compute the MWT of substantially larger random point sets than have previously been computed. ^1Though in this paper we summarize some empirical findings for input sets of up to 350 points, a variant of the algorithm has been implemented and tested on up to 40,000 points producing connected subgraphs [2]. Received May 29, 1996, and in revised form January 10, 1997.     

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.     

Computing a Minimum Weight Triangulation of a Sparse Point Set*

Investigating the minimum weight triangulation of a point set with constraint is an important approach for seeking the ultimate solution of the minimum weight triangulation problem. In this paper, we consider the minimum weight triangulation of a sparse point set, and present an O(n ⁴) algorithm to compute a triangulation of such a set. The property of sparse point set can be converted into a new sufficient condition for finding subgraphs of the minimum weight triangulation. A special point set is exhibited to show that our new subgraph of minimum weight triangulation cannot be found by any currently known methods.     

Approximation for Minimum Triangulations of Simplicial Convex 3-Polytopes

A minimum triangulation of a convex 3-polytope is a triangulation that contains the minimum number of tetrahedra over all its possible triangulations. Since finding minimum triangulations of convex 3-polytopes was recently shown to be NP-hard, it becomes significant to find algorithms that give good approximation. In this paper we give a new triangulation algorithm with an improved approximation ratio 2 - Ω(1/\sqrt n ) , where n is the number of vertices of the polytope. We further show that this is the best possible for algorithms that only consider the combinatorial structure of the polytopes. Received August 5, 2000, and in revised form March 29, 2001, and May 3, 2001. Online publication October 12, 2001.     

Increasing the Weight of Minimum Spanning Trees

The problems of computing the maximum increase in the weight of the minimum spanning trees of a graph caused by the removal of a given number of edges, or by finite increases in the weights of the edges, are investigated. For the case of edge removals, the problem is shown to be NP-hard and an Ω(1/log k)-approximation algorithm is presented for it, where (input parameter) k > 1 is the number of edges to be removed. The second problem is studied, assuming that the increase in the weight of an edge has an associated cost proportional to the magnitude of the change. An O(n³m² log(n²/m)) time algorithm is presented to solve it.     

最省砝码设置问题的数学模型

通过对砝码的最省设置问题的研究,建立了解决这一类问题的数学模型,并给出了一个有效、简便、操作程序化的求解算法.     

On the Value of a Random Minimum Weight Steiner Tree

Consider a complete graph on n vertices with edge weights chosen randomly and independently from an exponential distribution with parameter 1. Fix k vertices and consider the minimum weight Steiner tree which contains these vertices. We prove that with high probability the weight of this tree is (1+o(1))(k-1)(log n-log k)/n when k =o(n) and n.* Research supported in part by NSF grant DSM9971788 Research supported in part by NSF grants DMS-0106589, CCR-9987845 and by the State of New Jersey. Part of this research was done while visiting IBM T. J. Watson Research Center.     

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.     

Optimal Delaunay Triangulations

The Delaunay triangulation, in both classic and more generalized sense, is studied in this paper for minimizing the linear interpolation error (measure in L^P-norm) for a given function. The classic Delaunay triangulation can then be characterized as an optimal triangulation that minimizes the interpolation error for the isotropic function ‖x‖^2 among all the triangulations with a given set of vertices. For a more general function, a functiondependent Delaunay triangulation is then defined to be an optimal triangulation that minimizes the interpolation error for this function and its construction can be obtained by a simple lifting and projection procedure. The optimal Delaunay triangulation is the one that minimizes the interpolation error among all triangulations with the same number of vertices, i.e. the distribution of vertices are optimized in order to minimize the interpolation error. Such a function-depend entoptimal Delaunay triangulation is proved to exist for any given convex continuous function.On an optimal Delaunay triangulation associated with f, it is proved that △↓f at the interior vertices can be exactly recovered by the function values on its neighboring vertices.Since the optimal Delaunay triangulation is difficult to obtain in practice, the concept of nearly optimal triangulation is introduced and two sufficient conditions are presented for a triangulation to be nearly optimal.     

Minimum Weight and Dimension Formulas for Some Geometric Codes

The geometric codes are the duals of the codes defined by the designs associated with finite geometries. The latter are generalized Reed–Muller codes, but the geometric codes are, in general, not. We obtain values for the minimum weight of these codes in the binary case, using geometric constructions in the associated geometries, and the BCH bound from coding theory. Using Hamada's formula, we also show that the dimension of the dual of the code of a projective geometry design is a polynomial function in the dimension of the geometry.     

Triangulations in CGAL

This paper presents the main algorithmic and design choices that have been made to implement triangulations in the computational geometry algorithms library .     

关于数学期望型水平值逼近优化问题总极值的算法

本文研究用数学期望型水平值逼近一类优化问题总极值的算法,证明了算法所构造的数学期望型水平值迭代方程的解的存在唯一性,同时证明了方程的解是原来优化问题的总极值,并对可统一到该算法理论框架下的几种可实现算法进行了简要描述,数值实验结果验证了算法的有效性.     

关于适约三角剖分的计数

众所周知，适约三角剖分在地图运算中有着重要作用．本文对于平面上这种三角剖分的数目进行了探讨．同时，也提供了含有两个变量的精确公式．     

An Ant Colony Optimization Algorithm for the Minimum Weight Vertex Cover Problem

Given an undirected graph and a weighting function defined on the vertex set, the minimum weight vertex cover problem is to find a vertex subset whose total weight is minimum subject to the premise that the selected vertices cover all edges in the graph. In this paper, we introduce a meta-heuristic based upon the Ant Colony Optimization (ACO) approach, to find approximate solutions to the minimum weight vertex cover problem. In the literature, the ACO approach has been successfully applied to several well-known combinatorial optimization problems whose solutions might be in the form of paths on the associated graphs. A solution to the minimum weight vertex cover problem however needs not to constitute a path. The ACO algorithm proposed in this paper incorporates several new features so as to select vertices out of the vertex set whereas the total weight can be minimized as much as possible. Computational experiments are designed and conducted to study the performance of our proposed approach. Numerical results evince that the ACO algorithm demonstrates significant effectiveness and robustness in solving the minimum weight vertex cover problem.     

On the Number of Fair Triangulations

In this paper a special kind of triangulated maps on the sphere called fair triangulations is enumerated with the size of maps as parameter. Moreover, the number of several other kinds of triangulations are enumerated as well. Received June 18, 1997, Accepted June 12, 1998     

Irreducible Triangulations of the Klein Bottle

We determine the complete list of the irreducible triangulations of the Klein bottle, up to equivalence, analyzing their structures.     

Flipping Edges in Triangulations

In this paper we study the problem of flipping edges in triangulations of polygons and point sets. One of the main results is that any triangulation of a set of n points in general position contains at least edges that can be flipped. We also prove that O(n + k ² ) flips are sufficient to transform any triangulation of an n -gon with k reflex vertices into any other triangulation. We produce examples of n -gons with triangulations T and T' such that to transform T into T' requires Ω(n ² ) flips. Finally we show that if a set of n points has k convex layers, then any triangulation of the point set can be transformed into any other triangulation using at most O(kn) flips. Received May 13, 1997, and in revised form July 21, 1998, and February 1, 1999.     

Elementary Moves on Triangulations

It is proved that a triangulation of a polyhedron can always be transformed into any other triangulation of the polyhedron using only elementary moves. One consequence is that an additive function (valuation) defined only on simplices may always be extended to an additive function on all polyhedra.     

Acute Triangulations of Polygons

This paper proposes a combinatorial approach to planning non-colliding trajectories for a polygonal bar-and-joint framework with n vertices. It is based on a new class of simple motions induced by expansive one-degree-of-freedom mechanisms, which guarantee noncollisions by moving all points away from each other. Their combinatorial structure is captured by pointed pseudo-triangulations, a class of embedded planar graphs for which we give several equivalent characterizations and exhibit rich rigidity theoretic properties. The main application is an efficient algorithm for the Carpenter’s Rule Problem: convexify a simple bar-and-joint planar polygonal linkage using only non-self-intersecting planar motions. A step of the algorithm consists in moving a pseudo-triangulation-based mechanism along its unique trajectory in configuration space until two adjacent edges align. At the alignment event, a local alteration restores the pseudo-triangulation. The motion continues for O(n3) steps until all the points are in convex position. An erratum to this article is available at .