共查询到20条相似文献,搜索用时 531 毫秒
1.
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 dimensions d. 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. 相似文献
2.
Let S be a finite set of points in the Euclidean plane. Let G be a geometric graph in the plane whose point set is S. The stretch factor of G is the maximum ratio, among all points p and q in S, of the length of the shortest path from p to q in G over the Euclidean distance | pq|. Keil and Gutwin in 1989 [11] proved that the stretch factor of the Delaunay triangulation of a set of points S in the plane is at most 2 π/(3cos( π/6))≈2.42. Improving on this upper bound remains an intriguing open problem in computational geometry.In this paper we consider the special case when the points in S are in convex position. We prove that in this case the stretch factor of the Delaunay triangulation of S is at most ρ=2.33. 相似文献
3.
We construct a suitable B-spline representation for a family of bivariate spline functions with smoothness r≥1 and polynomial degree 3 r?1. They are defined on a triangulation with Powell–Sabin refinement. The basis functions have a local support, they are nonnegative, and they form a partition of unity. The construction involves the determination of triangles that must contain a specific set of points. We further consider a number of CAGD applications. We show how to define control points and control polynomials (of degree 2 r?1), and we provide an efficient and stable computation of the Bernstein–Bézier form of such splines. 相似文献
4.
A boundary conforming Delaunay mesh is a partitioning of a polyhedral domain into Delaunay simplices such that all boundary simplices satisfy the generalized Gabriel property. It’s dual is a Voronoi partition of the same domain which is preferable for Voronoi-box based finite volume schemes. For arbitrary 2D polygonal regions, such meshes can be generated in optimal time and size. For arbitrary 3D polyhedral domains,
however, this problem remains a challenge. The main contribution of this paper is to show that boundary conforming Delaunay
meshes for 3D polyhedral domains can be generated efficiently when the smallest input angle of the domain is bounded by arccos 1/3 ≈ 70.53°. In addition, well-shaped tetrahedra and an appropriate mesh size can be
obtained. Our new results are achieved by reanalyzing a classical Delaunay refinement algorithm. Note that our theoretical
guarantee on the input angle (70.53°) is still too strong for many practical situations. We further discuss variants of the
algorithm to relax the input angle restriction and to improve the mesh quality. 相似文献
5.
The Delaunay triangulation and the weighted Delaunay triangulation are not uniquely defined when the input set is degenerate. We present a new symbolic perturbation that allows to always define these triangulations in a unique way, as soon as the points are not all coplanar. No flat tetrahedron exists in the defined triangulation. The perturbation scheme is easy to code. It is implemented in cgal, and guarantees that both vertex insertion and vertex removal are fully robust. 相似文献
6.
It is well known that the complexity of the Delaunay
triangulation of $n$ points in $\RR ^d$, i.e., the number of its
simplices, can be $\Omega (n^{\lceil {d}/{2}\rceil })$. In
particular, in $\RR ^3$, the number of tetrahedra can be quadratic.
Put another way, if the points are uniformly distributed in a cube or a
ball, the expected complexity of the Delaunay triangulation is only
linear. The case of points distributed on a surface is of great
practical importance in reverse engineering since most surface
reconstruction algorithms first construct the Delaunay triangulation
of a set of points measured on a surface.
In this paper we bound the complexity of the Delaunay triangulation
of points distributed on the boundary of a given polyhedron. Under a
mild uniform sampling condition, we provide deterministic asymptotic
bounds on the complexity of the three-dimensional Delaunay triangulation of the
points when the sampling density increases. More precisely, we show
that the complexity is $O(n^{1.8})$ for general polyhedral surfaces
and $O(n\sqrt{n})$ for convex polyhedral surfaces.
Our proof uses a geometric result of independent interest that states
that the medial axis of a surface is well approximated by a subset of
the Voronoi vertices of the sample points. 相似文献
7.
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. 相似文献
8.
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. 相似文献
9.
The starting point of the analysis in this paper is the following situation: "In a bounded domain in 2, let a finite set of points be given. A triangulation of that domain has to be found, whose vertices are the given points and which is `suitable' for the linear conforming Finite Element Method (FEM)." The result of this paper is that for the discrete Poisson equation and under some weak additional assumptions, only the use of Delaunay triangulations preserves the maximum principle. 相似文献
10.
Delaunay refinement is a technique for generating unstructured meshes of triangles for use in interpolation, the finite element method, and the finite volume method. In theory and practice, meshes produced by Delaunay refinement satisfy guaranteed bounds on angles, edge lengths, the number of triangles, and the grading of triangles from small to large sizes. This article presents an intuitive framework for analyzing Delaunay refinement algorithms that unifies the pioneering mesh generation algorithms of L. Paul Chew and Jim Ruppert, improves the algorithms in several minor ways, and most importantly, helps to solve the difficult problem of meshing nonmanifold domains with small angles. Although small angles inherent in the input geometry cannot be removed, one would like to triangulate a domain without creating any new small angles. Unfortunately, this problem is not always soluble. A compromise is necessary. A Delaunay refinement algorithm is presented that can create a mesh in which most angles are 30° or greater and no angle is smaller than arcsin[(
, where φ60°is the smallest angle separating two segments of the input domain. New angles smaller than 30° appear only near input angles smaller than 60°. In practice, the algorithm's performance is better than these bounds suggest. Another new result is that Ruppert's analysis technique can be used to reanalyze one of Chew's algorithms. Chew proved that his algorithm produces no angle smaller than 30° (barring small input angles), but without any guarantees on grading or number of triangles. He conjectures that his algorithm offers such guarantees. His conjecture is conditionally confirmed here: if the angle bound is relaxed to less than 26.5°, Chew's algorithm produces meshes (of domains without small input angles) that are nicely graded and size-optimal. 相似文献
11.
A Delaunay tetrahedralization of $n$ vertices is exhibited for which
a straight line can pass through the interiors of
$\Theta(n^2)$ tetrahedra.
This solves an open problem of Amenta,
who asked whether a line can stab more than $O(n)$ tetrahedra.
The construction generalizes to higher dimensions: in $d$ dimensions,
a line can stab the interiors of $\Theta(n^{\lceil d / 2 \rceil})$
Delaunay $d$-simplices.
The relationship between a Delaunay triangulation and
a convex polytope yields another result:
a two-dimensional slice of a $d$-dimensional $n$-vertex polytope
can have $\Theta(n^{\lfloor d / 2 \rfloor})$ facets.
This last result was first demonstrated by Amenta and Ziegler,
but the construction given here is simpler and more intuitive. 相似文献
12.
Given a triangulation of points in the plane and a function on the points, one may consider the Dirichlet energy, which is
related to the Dirichlet energy of a smooth function. In fact, the Dirichlet energy can be derived from a finite element approximation.
S. Rippa showed that the Dirichlet energy (which he refers to as the “roughness”) is minimized by the Delaunay triangulation
by showing that each edge flip which makes an edge Delaunay decreases the energy. In this paper, we introduce a Dirichlet
energy on a weighted triangulation which is a generalization of the energy on unweighted triangulations and an analogue of
the smooth Dirichlet energy on a domain. We show that this Dirichlet energy has the property that each edge flip which makes
an edge weighted Delaunay decreases the energy. The proof is done by a direct calculation, and so gives an alternate proof
of Rippa’s result. 相似文献
13.
Using new number-theoretic bounds on the denominators of unit fractions summing up to one, we show that in any dimension d
≥ 4 there is only one d-dimensional reflexive simplex having maximal volume. Moreover, only these reflexive simplices can
admit an edge that has the maximal number of lattice points possible for an edge of a reflexive simplex. In general, these
simplices are also expected to contain the largest number of lattice points even among all lattice polytopes with only one
interior lattice point. Translated in algebro-geometric language, our main theorem yields a sharp upper bound on the anticanonical
degree of d-dimensional Q-factorial Gorenstein toric Fano varieties with Picard number one, e.g., of weighted projective spaces
with Gorenstein singularities. 相似文献
14.
We describe an algorithm which, for any piecewise linear complex (PLC) in 3D, builds a Delaunay triangulation conforming to this PLC. The algorithm has been implemented, and yields in practice a relatively small number of Steiner points due to the fact that it adapts to the local geometry of the PLC. It is, to our knowledge, the first practical algorithm devoted to this problem. 相似文献
15.
On each simplex in a complex of r-dimensional simplices a rational function of special form is constructed which is composed of a polynomial part and a rational part.It is proved in this paper that these pieceivise rational functions can be patched together sufficiently smoothly to form a uniquely determined rational spline by certain interpolation conditions. 相似文献
16.
The existence of minimum norm properties for even degree polynomial splines, analogous to the. ones known for odd degree splines, is investigated within the framework of the theory of topological spline systems. It is shown that such properties cannot exist for even degree splines interpolating functions halfway between the partition points. For another class of even degree spline functions, however, which hterpolate the local integrals of given functions with respect to the partitions, the seeked minimum norm properties can be proved. This is carried out by first investigating a generalized problem within the theory of spline systems and then deriving corresponding conclusions. As a corollary the existence of spline systems with respect to differential operators of fractional degree is obtained. 相似文献
17.
We consider a new construction, the weak Delaunay triangulation of a finite point set in a metric space, which contains as a subcomplex the traditional ( strong) Delaunay triangulation. The two simplicial complexes turn out to be equal for point sets in Euclidean space, as well as
in the (hemi)sphere, hyperbolic space, and certain other geometries. There are weighted and approximate versions of the weak
and strong complexes in all these geometries, and we prove equality theorems in those cases also. On the other hand, for discrete
metric spaces the weak and strong complexes are decidedly different. We give a short empirical demonstration that weak Delaunay
complexes can lead to dramatically clean results in the problem of estimating the homology groups of a manifold represented
by a finite point sample.
相似文献
18.
We prove theorems on locally antipodal Delaunay sets. The main result is the proof of a uniqueness theorem for locally antipodal Delaunay sets with a given 2 R-cluster. This theorem implies, in particular, a new proof of a theorem stating that a locally antipodal Delaunay set all of whose 2 R-clusters are equivalent is a regular system, i.e., a Delaunay set on which a crystallographic group acts transitively. 相似文献
19.
We prove some new relations between functions defined as shadows of cones (cone splines) and simplices (simplex splines). We use them to show how an s-variate simplex spline of some order k can be written as a sum of k+1 (s-l)-variate simplex splines of order k-1. A recurrence relation on the spatial dimension of the simplex spline, s, is proposed as an interesting alternative to the recurrence relation in [17], where one uses the order k for recursion, but not the spatial dimension s. 相似文献
20.
It is proved that the shape of the typical cell of
a Delaunay tessellation, derived from a stationary Poisson point process in d-dimensional Euclidean space, tends to the shape of a regular simplex, given
that the volume of the typical cell tends to infinity. This follows from an
estimate for the probability that the typical cell deviates by a given amount
from regularity, given that its volume is large. As a tool for the proof,
a stability result for simplices is established. 相似文献
|