共查询到20条相似文献,搜索用时 78 毫秒
1.
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
R3 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 R3 (e.g. the planar polygons in a
polyhedron). Our bound is deterministic and the constants are
explicitly given. 相似文献
2.
3.
《Computational Geometry》2007,36(1):52-65
For hydrologic applications, terrain models should have few local minima, and drainage lines should coincide with edges. We show that triangulating a set of points with elevations such that the number of local minima of the resulting terrain is minimized is NP-hard for degenerate point sets. The same result applies when there are no degeneracies for higher-order Delaunay triangulations. Two heuristics are presented to reduce the number of local minima for higher-order Delaunay triangulations, which start out with the Delaunay triangulation. We give efficient algorithms for their implementation, and test on real-world data how well they perform. We also study another desirable drainage characteristic, few valley components, and how to obtain it for higher-order Delaunay triangulations. This gives rise to a third heuristic. Tables and visualizations show how the heuristics perform for the drainage characteristics on real-world data. 相似文献
4.
Alper Üngör 《Computational Geometry》2009,42(2):109-118
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.1 相似文献
5.
Delaunay triangulation and its complementary structure the Voronoi polyhedra form two of the most fundamental constructs of computational geometry. Delaunay triangulation offers an efficient method for generating high-quality triangulations. However, the generation of Delaunay triangulations in 3D with Watson's algorithm, leads to the appearance of silver tetrahedra, in a relatively large percentage. A different method for generating high-quality tetrahedralizations, based on Delaunay triangulation and not presenting the problem of sliver tetrahedra, is presented. The method consists in a tetrahedra division procedure and an efficient method for optimizing tetrahedral meshes, based on the application of a set of topological Delaunay transformations for tetrahedra and a technique for node repositioning. The method is robust and can be applied to arbitrary unstructured tetrahedral meshes, having as a result the generation of high-quality adaptive meshes with varying density, totally eliminating the appearance of sliver elements. In this way it offers a convenient and highly flexible algorithm for implementation in a general purpose 3D adaptive finite element analysis system. Applications to various engineering problems are presented 相似文献
6.
《European Journal of Operational Research》2006,173(3):717-728
We propose a new technique to perform unsupervised data classification (clustering) based on density induced metric and non-smooth optimization. Our goal is to automatically recognize multidimensional clusters of non-convex shape. We present a modification of the fuzzy c-means algorithm, which uses the data induced metric, defined with the help of Delaunay triangulation. We detail computation of the distances in such a metric using graph algorithms. To find optimal positions of cluster prototypes we employ the discrete gradient method of non-smooth optimization. The new clustering method is capable to identify non-convex overlapped d-dimensional clusters. 相似文献
7.
Maria-Cecilia Rivara 《Applied Numerical Mathematics》2009,59(9):2218-2235
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. 相似文献
8.
Jeff Erickson 《Discrete and Computational Geometry》2005,33(1):83-115
The spread of a finite set of points is the ratio between the
longest and shortest pairwise distances. We prove that the Delaunay
triangulation of any set of $n$ points in~$\Real^3$ with spread
$\Delta$ has complexity $O(\Delta^3)$. This bound is tight in the
worst case for all $\Delta = O(\sqrt{n})$. In particular, the
Delaunay triangulation of any dense point set has linear complexity.
We also generalize this upper bound to regular triangulations of
$k$-ply systems of balls, unions of several dense point sets, and
uniform samples of smooth surfaces. On the other hand, for any $n$
and $\Delta = O(n)$, we construct a regular triangulation of
complexity $\Omega(n\Delta)$ whose $n$ vertices have spread $\Delta$. 相似文献
9.
General-Dimensional Constrained Delaunay and Constrained Regular Triangulations, I: Combinatorial Properties 总被引:2,自引:0,他引:2
Jonathan Richard Shewchuk 《Discrete and Computational Geometry》2008,39(1-3):580-637
Two-dimensional constrained Delaunay triangulations are geometric structures that are popular for interpolation and mesh generation
because they respect the shapes of planar domains, they have “nicely shaped” triangles that optimize several criteria, and
they are easy to construct and update. The present work generalizes constrained Delaunay triangulations (CDTs) to higher dimensions
and describes constrained variants of regular triangulations, here christened weighted CDTs and constrained regular triangulations. CDTs and weighted CDTs are powerful and practical models of geometric domains, especially in two and three dimensions.
The main contributions are rigorous, theory-tested definitions of CDTs and piecewise linear complexes (geometric domains that
incorporate nonconvex faces with “internal” boundaries), a characterization of the combinatorial properties of CDTs and weighted
CDTs (including a generalization of the Delaunay Lemma), the proof of several optimality properties of CDTs when they are
used for piecewise linear interpolation, and a simple and useful condition that guarantees that a domain has a CDT. These
results provide foundations for reasoning about CDTs and proving the correctness of algorithms. Later articles in this series
discuss algorithms for constructing and updating CDTs.
Supported in part by the National Science Foundation under Awards CMS-9318163, ACI-9875170, CMS-9980063, CCR-0204377, CCF-0430065,
and EIA-9802069, in part by the Advanced Research Projects Agency and Rome Laboratory, Air Force Materiel Command, USAF under
agreement number F30602-96-1-0287, in part by an Alfred P. Sloan Research Fellowship, and in part by gifts from the Okawa
Foundation and Intel. The views in this document are those of the author. They are not endorsed by the sponsors or the U.S.
Government. 相似文献
10.
David Glickenstein 《Discrete and Computational Geometry》2007,38(4):651-664
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. 相似文献
11.
We introduce a master–worker framework for parallel global optimization of computationally expensive functions using response surface models. In particular, we parallelize two radial basis function (RBF) methods for global optimization, namely, the RBF method by Gutmann [Gutmann, H.M., 2001a. A radial basis function method for global optimization. Journal of Global Optimization 19(3), 201–227] (Gutmann-RBF) and the RBF method by Regis and Shoemaker [Regis, R.G., Shoemaker, C.A., 2005. Constrained global optimization of expensive black box functions using radial basis functions, Journal of Global Optimization 31, 153–171] (CORS-RBF). We modify these algorithms so that they can generate multiple points for simultaneous evaluation in parallel. We compare the performance of the two parallel RBF methods with a parallel multistart derivative-based algorithm, a parallel multistart derivative-free trust-region algorithm, and a parallel evolutionary algorithm on eleven test problems and on a 6-dimensional groundwater bioremediation application. The results indicate that the two parallel RBF algorithms are generally better than the other three alternatives on most of the test problems. Moreover, the two parallel RBF algorithms have comparable performances on the test problems considered. Finally, we report good speedups for both parallel RBF algorithms when using a small number of processors. 相似文献
12.
《Journal of Computational and Applied Mathematics》2002,145(2):505-517
This paper studies adaptive thinning strategies for approximating a large set of scattered data by piecewise linear functions over triangulated subsets. Our strategies depend on both the locations of the data points in the plane, and the values of the sampled function at these points—adaptive thinning. All our thinning strategies remove data points one by one, so as to minimize an estimate of the error that results by the removal of a point from the current set of points (this estimate is termed “anticipated error”). The thinning process generates subsets of “most significant” points, such that the piecewise linear interpolants over the Delaunay triangulations of these subsets approximate progressively the function values sampled at the original scattered points, and such that the approximation errors are small relative to the number of points in the subsets. We design various methods for computing the anticipated error at reasonable cost, and compare and test the performance of the methods. It is proved that for data sampled from a convex function, with the strategy of convex triangulation, the actual error is minimized by minimizing the best performing measure of anticipated error. It is also shown that for data sampled from certain quadratic polynomials, adaptive thinning is equivalent to thinning which depends only on the locations of the data points—nonadaptive thinning. Based on our numerical tests and comparisons, two practical adaptive thinning algorithms are proposed for thinning large data sets, one which is more accurate and another which is faster. 相似文献
13.
The maximin LHD problem calls for arranging N points in a k-dimensional grid so that no pair of points share a coordinate and the distance of the closest pair of points is as large as possible. In this paper we propose to tackle this problem by heuristic algorithms belonging to the Iterated Local Search (ILS) family and show through some computational experiments that the proposed algorithms compare very well with different heuristic approaches in the established literature. 相似文献
14.
V. T. Rajan 《Discrete and Computational Geometry》1994,12(1):189-202
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. 相似文献
15.
Jean-Daniel Boissonnat Ramsay Dyer Arijit Ghosh 《Foundations of Computational Mathematics》2018,18(2):399-431
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. 相似文献
16.
The paper describes a parallel algorithm for computing an n-dimensional Delaunay tessellation using a divide-conquer strategy. Its implementation (using MPI library for C) in the case
n = 2, relied on restricted areas to discard non-Delaunay edges, is executed easily on PC clusters. We shows that the convexity
is a crucial factor of efficiency of the parallel implementation over the corresponding sequential one. 相似文献
17.
K. S. Kobylkin 《Proceedings of the Steklov Institute of Mathematics》2017,299(1):106-112
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 ∈ R2 and λ > 0 whose interior does not contain triangulation vertices and whose boundary contains this pair of vertices and only it, where ?(p, λ) = p + λ? = {x ∈ R2: 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. 相似文献
18.
Olivier Devillers Monique Teillaud 《Computational Geometry》2011,44(3):160-168
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. 相似文献
19.
Jean-Daniel Boissonnat Frank Nielsen Richard Nock 《Discrete and Computational Geometry》2010,44(2):281-307
The Voronoi diagram of a finite set of objects is a fundamental geometric structure that subdivides the embedding space into
regions, each region consisting of the points that are closer to a given object than to the others. We may define various
variants of Voronoi diagrams depending on the class of objects, the distance function and the embedding space. In this paper,
we investigate a framework for defining and building Voronoi diagrams for a broad class of distance functions called Bregman
divergences. Bregman divergences include not only the traditional (squared) Euclidean distance but also various divergence
measures based on entropic functions. Accordingly, Bregman Voronoi diagrams allow one to define information-theoretic Voronoi
diagrams in statistical parametric spaces based on the relative entropy of distributions. We define several types of Bregman
diagrams, establish correspondences between those diagrams (using the Legendre transformation), and show how to compute them
efficiently. We also introduce extensions of these diagrams, e.g., k-order and k-bag Bregman Voronoi diagrams, and introduce Bregman triangulations of a set of points and their connection with Bregman Voronoi
diagrams. We show that these triangulations capture many of the properties of the celebrated Delaunay triangulation. 相似文献
20.
The aim of this paper is to introduce a fast and efficient new two-grid method to solve the d-dimensional (d=1,2,3) Poisson elliptic equations. The finite difference equations at all interior grid points form a large sparse linear system, which needs to be solved efficiently. The solution cost of this sparse linear system usually dominates the total cost of solving the discretized partial differential equation. The finite difference equations are based on applying a finite difference scheme of two- and four-orders (compact finite difference method) for discretizing the spatial derivative. The obtained linear systems of Poisson elliptic equations have been solved by a new two-grid (NTG) method and we also note that the NTG method which is used for solving the large sparse linear systems is faster and more effective than that of the standard two-grid method. We utilize the local Fourier analysis to show that the spectral radius of the new two-grid method for 1D and 2D models is less than that of the standard two-grid method. As well as, we expand the corresponding algorithm to the new multi-grid method. The numerical examples show the efficiency of the new algorithms for solving the d-dimensional Poisson equations. 相似文献