Manifold Reconstruction in Arbitrary Dimensions Using Witness Complexes

It is a well-established fact that the witness complex is closely related to the restricted Delaunay triangulation in low dimensions. Specifically, it has been proved that the witness complex coincides with the restricted Delaunay triangulation on curves, and is still a subset of it on surfaces, under mild sampling conditions. In this paper, we prove that these results do not extend to higher-dimensional manifolds, even under strong sampling conditions such as uniform point density. On the positive side, we show how the sets of witnesses and landmarks can be enriched, so that the nice relations that exist between restricted Delaunay triangulation and witness complex hold on higher-dimensional manifolds as well. We derive from our structural results an algorithm that reconstructs manifolds of any arbitrary dimension or co-dimension at different scales. The algorithm combines a farthest-point refinement scheme with a vertex pumping strategy. It is very simple conceptually, and it does not require the input point sample to be sparse. Its running time is bounded by c(d)n ², where n is the size of the input point cloud, and c(d) is a constant depending solely (yet exponentially) on the dimension d of the ambient space. Although this running time makes our reconstruction algorithm rather theoretical, recent work has shown that a variant of our approach can be made tractable in arbitrary dimensions, by building upon the results of this paper. This work was done while S.Y. Oudot was a post-doctoral fellow at Stanford University. His email there is no longer valid.     

A weak characterisation of the Delaunay triangulation

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.      

On delaunay oriented matroids for convex distance functions

For any finite point setS inE ^d, an oriented matroid DOM (S) can be defined in terms of howS is partitioned by Euclidean hyperspheres. This oriented matroid is related to the Delaunay triangulation ofS and is realizable, because of thelifting property of Delaunay triangulations. We prove that the same construction of aDelaunay oriented matroid can be performed with respect to any smooth, strictly convex distance function in the planeE ² (Theorem 3.5). For these distances, the existence of a Delaunay oriented matroid cannot follow from a lifting property, because Delaunay triangulations might be nonregular (Theorem 4.2(i). This is related to the fact that the Delaunay oriented matroid can be nonrealizable (Theorem 4.2(ii). This research was partially supported by the Spanish Grant DGICyT PB 92/0498-C02 and the David and Lucile Packard Foundation.     

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.     

Efficiently updating constrained Delaunay triangulations

TheConstrained Delaunay Triangulation of a set of obstacle line segments in the plane is the Delaunay triangulation of the endpoint set of these obstacles with the restriction that the edge set of the triangulation contains all these obstacles. In this paper we present an optimal (logn +k) algorithm for inserting an obstacle line segment or deleting an obstacle edge in the constrained Delaunay triangulation of a set ofn obstacle line segments in the plane. Herek is the number of Delaunay edges deleted and added in the triangulation during the updates.This work is supported by NSERC grant OPG0041629.     

On the stretch factor of Delaunay triangulations of points in convex position

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.     

Nice Point Sets Can Have Nasty Delaunay Triangulations

   Abstract. We consider the complexity of Delaunay triangulations of sets of points in R ³ under certain practical geometric constraints. The spread of a set of points is the ratio between the longest and shortest pairwise distances. We show that in the worst case, the Delaunay triangulation of n points in R ³ with spread Δ has complexity Ω(min{ Δ³, nΔ, n² }) and O(min{ Δ⁴, n ² }). For the case

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.     

Contractivity and Analyticity in l p of Some Approximation of the Heat Equation

We consider the lumped mass method with piecewise linear finite elements in two dimensions. When the triangulation is of Delaunay type it is known that the discrete scheme satisfies a maximum principle. In this work we pursue the analysis and prove that the discrete semi-group is l ^p contractive in a sector, which implies smoothing effects and provide some resolvent estimates.     

A randomized Delaunay triangulation heuristic for the Euclidean Steiner tree problem in <Emphasis Type="Italic">ℜ</Emphasis><Superscript><Emphasis Type="Italic">d</Emphasis></Superscript>

We present a heuristic for the Euclidean Steiner tree problem in ℜ ^d for d≥2. The algorithm utilizes the Delaunay triangulation to generate candidate Steiner points for insertion, the minimum spanning tree to identify the Steiner points to remove, and second-order cone programming to optimize the location of the remaining Steiner points. Unlike other ESTP heuristics relying upon Delaunay triangulation, we insert Steiner points probabilistically into Delaunay triangles to achieve different subtrees on subsets of terminal points. We govern this neighbor generation procedure with a local search framework that extends effectively into higher dimensions. We present computational results on benchmark test problems in ℜ ^d for 2≤d≤5.     

Triangulation de Delaunay et Triangulation des Tores

We present a construction of triangulations of the torus \mathbbTⁿ{\mathbb{T}^n} with 2 ⁿ⁺¹−1 vertices, starting from the Delaunay triangulation of a generic lattices. The typical example is the Kühnel–Lassmann triangulation, with help of the lattice A^*_n{A^{*}_{n}} . Concerning this triangulation, we also prove a result of unicity for some values of n.     

Improved heuristics for the minimum weight triangulation problem

Given a planar point setS, a triangulation ofS is a maximal set of non-intersecting line segments connecting the points. The minimum weight triangulation problem is to find a triangulation ofS such that the sum of the lengths of the line segments in it is the smallest. No polynomial time algorithm is known to produce the optimal or even a constant approximation of the optimal solution, and it is also unknown whether the problem is NP-hard. In this paper, we propose two improved heuristics, which triangulate a set ofn points in a plane inO(n ³) time and never do worse than the minimum spanning tree triangulation algorithm given by Lingas and the greedy spanning tree triangulation algorithm given by Heath and Pemmaraju. These two algorithms both produce an optimal triangulation if the points are the vertices of a convex polygon, and also do the same in some special cases.     

Quality mesh generation for molecular skin surfaces using restricted union of balls

Quality surface meshes for molecular models are desirable in the studies of protein shapes and functionalities. However, there is still no robust software that is capable to generate such meshes with good quality. In this paper, we present a Delaunay-based surface triangulation algorithm generating quality surface meshes for the molecular skin model. We expand the restricted union of balls along the surface and generate an ε-sampling of the skin surface incrementally. At the same time, a quality surface mesh is extracted from the Delaunay triangulation of the sample points. The algorithm supports robust and efficient implementation and guarantees the mesh quality and topology as well. Our results facilitate molecular visualization and have made a contribution towards generating quality volumetric tetrahedral meshes for the macromolecules.     

Quot Functors for Deligne-Mumford Stacks

Abstract

Given a separated and locally finitely-presented Deligne-Mumford stack 𝒳 over an algebraic space S, and a locally finitely-presented 𝒪_𝒳-module ?, we prove that the Quot functor Quot(?/𝒳/S) is represented by a separated and locally finitely-presented algebraic space over S. Under additional hypotheses, we prove that the connected components of Quot(?/𝒳/S) are quasi-projective over S.     

Metrizability of Clifford topological semigroups

We prove that a countably compact Clifford topological semigroup S is metrizable if and only if the set E={e∈S:ee=e} of idempotents of S is a metrizable G _δ -set in S.     

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.     

Primal Dividing and Dual Pruning: Output-Sensitive Construction of Four-Dimensional Polytopes and Three-Dimensional Voronoi Diagrams

In this paper, we give an algorithm for output-sensitive construction of an f-face convex hull of a set of n points in general position in E ⁴ . Our algorithm runs in time and uses O(n+f) space. This is the first algorithm within a polylogarithmic factor of optimal time over the whole range of f. By a standard lifting map, we obtain output-sensitive algorithms for the Voronoi diagram or Delaunay triangulation in E ³ and for the portion of a Voronoi diagram that is clipped to a convex polytope. Our approach simplifies the ``ultimate convex hull algorithm' of Kirkpatrick and Seidel in E ² and also leads to improved output-sensitive results on constructing convex hulls in E ^d for any even constant d > 4. Received August 3, 1995, and in revised form September 19, 1996.     

Conforming Delaunay triangulations in 3D

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.     

A minimal triangulation of complex projective plane admitting a chess colouring of four-dimensional simplices

We construct and study a new 15-vertex triangulation X of the complex projective plane ℂP². The automorphism group of X is isomorphic to S ₄ × S ₃. We prove that the triangulation X is the minimal (with respect to the number of vertices) triangulation of ℂP² admitting a chess colouring of four-dimensional simplices. We provide explicit parametrizations for the simplices of X and show that the automorphism group of X can be realized as a group of isometries of the Fubini-Study metric. We find a 33-vertex subdivision $ \bar X $ \bar X of the triangulation X such that the classical moment mapping μ: ℂP² → Δ² is a simplicial mapping of the triangulation $ \bar X $ \bar X onto the barycentric subdivision of the triangle Δ². We study the relationship of the triangulation X with complex crystallographic groups.     

Coloring Graphs with Constraints on Connectivity

A graph G has maximal local edge‐connectivity k if the maximum number of edge‐disjoint paths between every pair of distinct vertices x and y is at most k. We prove Brooks‐type theorems for k‐connected graphs with maximal local edge‐connectivity k, and for any graph with maximal local edge‐connectivity 3. We also consider several related graph classes defined by constraints on connectivity. In particular, we show that there is a polynomial‐time algorithm that, given a 3‐connected graph G with maximal local connectivity 3, outputs an optimal coloring for G. On the other hand, we prove, for , that k‐colorability is NP‐complete when restricted to minimally k‐connected graphs, and 3‐colorability is NP‐complete when restricted to ‐connected graphs with maximal local connectivity k. Finally, we consider a parameterization of k‐colorability based on the number of vertices of degree at least , and prove that, even when k is part of the input, the corresponding parameterized problem is FPT.