International audience

Abstract We present criteria for establishing a triangulation of a manifold. Given a manifold M, a simplicial complex $${\mathscr {A}}$$ A , and a map H from the underlying space of $${\mathscr {A}}$$ A to M, our criteria are presented in local coordinate charts for M, and ensure that H is a homeomorphism. These criteria do not require a differentiable structure, or even an explicit metric on M. No Delaunay property of $${\mathscr {A}}$$ A is assumed. The result provides a triangulation guarantee for algorithms that construct a simplicial complex by working in local coordinate patches. Because the criteria are easily verified in such a setting, they are expected to be of general use.

Abstract. Isomanifolds are the generalization of isosurfaces to arbitrary dimension and codimension, i.e., submanifolds of [Formula: see text] defined as the zero set of some multivariate multivalued smooth function [Formula: see text], where [Formula: see text] is the intrinsic dimension of the manifold. A natural way to approximate a smooth isomanifold [Formula: see text] is to consider its piecewise linear (PL) approximation [Formula: see text] based on a triangulation [Formula: see text] of the ambient space [Formula: see text]. In this paper, we describe a simple algorithm to trace isomanifolds from a given starting point. The algorithm works for arbitrary dimensions [Formula: see text] and [Formula: see text], and any precision [Formula: see text]. Our main result is that, when [Formula: see text] (or [Formula: see text]) has bounded complexity, the complexity of the algorithm is polynomial in [Formula: see text] and [Formula: see text] (and unavoidably exponential in [Formula: see text]). Since it is known that for [Formula: see text], [Formula: see text] is [Formula: see text]-close and isotopic to [Formula: see text], our algorithm produces a faithful PL-approximation of isomanifolds of bounded complexity in time polynomial in [Formula: see text]. Combining this algorithm with dimensionality reduction techniques, the dependency on [Formula: see text] in the size of [Formula: see text] can be completely removed with high probability. We also show that the algorithm can handle isomanifolds with boundary and, more generally, isostratifolds. The algorithm for isomanifolds with boundary has been implemented and experimental results are reported, showing that it is practical and can handle cases that are far ahead of the state-of-the-art.

International audience

Abstract Randomized incremental construction (RIC) is one of the most important paradigms for building geometric data structures. Clarkson and Shor developed a general theory that led to numerous algorithms which are both simple and efficient in theory and in practice. Randomized incremental constructions are usually space-optimal and time-optimal in the worst case, as exemplified by the construction of convex hulls, Delaunay triangulations, and arrangements of line segments. However, the worst-case scenario occurs rarely in practice and we would like to understand how RIC behaves when the input is nice in the sense that the associated output is significantly smaller than in the worst case. For example, it is known that the Delaunay triangulation of nicely distributed points in $${\mathbb {E}}^d$$ E d or on polyhedral surfaces in $${\mathbb {E}}^3$$ E 3 has linear complexity, as opposed to a worst-case complexity of $$\Theta (n^{\lfloor d/2\rfloor })$$ Θ ( n ⌊ d / 2 ⌋ ) in the first case and quadratic in the second. The standard analysis does not provide accurate bounds on the complexity of such cases and we aim at establishing such bounds in this paper. More precisely, we will show that, in the two cases above and variants of them, the complexity of the usual RIC is $$O(n\log n)$$ O ( n log n ) , which is optimal. In other words, without any modification, RIC nicely adapts to good cases of practical value. At the heart of our proof is a bound on the complexity of the Delaunay triangulation of random subsets of $${\varepsilon }$$ ε -nets. Along the way, we prove a probabilistic lemma for sampling without replacement, which may be of independent interest.

Abstract We consider the following setting: suppose that we are given a manifold M in $${\mathbb {R}}^d$$ R d with positive reach. Moreover assume that we have an embedded simplical complex $${\mathcal {A}}$$ A without boundary, whose vertex set lies on the manifold, is sufficiently dense and such that all simplices in $${\mathcal {A}}$$ A have sufficient quality. We prove that if, locally, interiors of the projection of the simplices onto the tangent space do not intersect, then $${\mathcal {A}}$$ A is a triangulation of the manifold, that is, they are homeomorphic.

Abstract We quantise Whitney’s construction to prove the existence of a triangulation for any $$C^2$$ C2 manifold, so that we get an algorithm with explicit bounds. We also give a new elementary proof, which is completely geometric.

Given a set P of n points and a constant k, we are interested in computing the persistent homology of the Čech filtration of P for the k-distance, and investigate the effectiveness of dimensionality reduction for this problem, answering an open question of Sheehy [Proc. SoCG, 2014]. We show that any linear transformation that preserves pairwise distances up to a (1±ε) multiplicative factor, must preserve the persistent homology of the Čech filtration up to a factor of (1-ε)^{-1}. Our results also show that the Vietoris-Rips and Delaunay filtrations for the k-distance, as well as the Čech filtration for the approximate k-distance of Buchet et al. are preserved up to a (1±ε) factor. We also prove extensions of our main theorem, for point sets (i) lying in a region of bounded Gaussian width or (ii) on a low-dimensional manifold, obtaining the target dimension bounds of Lotz [Proc. Roy. Soc. , 2019] and Clarkson [Proc. SoCG, 2008 ] respectively.

In this article, we extend the notions of dominated vertex and strong collapse of a simplicial complex as introduced by J. Barmak and E. Miniam. We say that a simplex (of any dimension) is dominated if its link is a simplicial cone. Domination of edges appears to be a very powerful concept, especially when applied to flag complexes. We show that edge collapse (removal of dominated edges) in a flag complex can be performed using only the 1-skeleton of the complex. Furthermore, the residual complex is a flag complex as well. Next we show that, similar to the case of strong collapses, we can use edge collapses to reduce a flag filtration ℱ to a smaller flag filtration ℱ^c with the same persistence. Here again, we only use the 1-skeletons of the complexes. The resulting method to compute ℱ^c is simple and extremely efficient and, when used as a preprocessing for persistence computation, leads to gains of several orders of magnitude w.r.t the state-of-the-art methods (including our previous approach using strong collapse). The method is exact, irrespective of dimension, and improves performance of persistence computation even in low dimensions. This is demonstrated by numerous experiments on publicly available data.

International audience

In this article, we focus on the problem of computing Persistent Homology of a flag tower, i.e. a sequence of flag complexes connected by simplicial maps. We show that if we restrict the class of simplicial complexes to flag complexes, we can achieve decisive improvement in terms of time and space complexities with respect to previous work. We show that strong collapses of flag complexes can be computed in time O(k^2v^2) where v is the number of vertices of the complex and k is the maximal degree of its graph. Moreover we can strong collapse a flag complex knowing only its 1-skeleton and the resulting complex is also a flag complex. When we strong collapse the complexes in a flag tower, we obtain a reduced sequence that is also a flag tower we call the core flag tower. We then convert the core flag tower to an equivalent filtration to compute its PH. Here again, we only use the 1-skeletons of the complexes. The resulting method is simple and extremely efficient.

Randomized incremental construction (RIC) is one of the most important paradigms for building geometric data structures. Clarkson and Shor developed a general theory that led to numerous algorithms that are both simple and efficient in theory and in practice. Randomized incremental constructions are most of the time space and time optimal in the worst-case, as exemplified by the construction of convex hulls, Delaunay triangulations and arrangements of line segments. However, the worst-case scenario occurs rarely in practice and we would like to understand how RIC behaves when the input is nice in the sense that the associated output is significantly smaller than in the worst-case. For example, it is known that the Delaunay triangulations of nicely distributed points on polyhedral surfaces in E^3 has linear complexity, as opposed to a worst-case quadratic complexity. The standard analysis does not provide accurate bounds on the complexity of such cases and we aim at establishing such bounds in this paper. More precisely, we will show that, in the case of nicely distributed points on polyhedral surfaces, the complexity of the usual RIC is O(n log n), which is optimal. In other words, without any modification, RIC nicely adapts to good cases of practical value. Our proofs also work for some other notions of nicely distributed point sets, such as (epsilon, kappa)-samples. Along the way, we prove a probabilistic lemma for sampling without replacement, which may be of independent interest.

The construction of anisotropic triangulations is desirable for various applications, such as the numerical solving of partial differential equations and the representation of surfaces in graphics. To solve this notoriously difficult problem in a practical way, we introduce the discrete Riemannian Voronoi diagram, a discrete structure that approximates the Riemannian Voronoi diagram. This structure has been implemented and was shown to lead to good triangulations in $\mathbb{R}^2$ and on surfaces embedded in $\mathbb{R}^3$ as detailed in our experimental companion paper. In this paper, we study theoretical aspects of our structure. Given a finite set of points $\mathcal{P}$ in a domain $\Omega$ equipped with a Riemannian metric, we compare the discrete Riemannian Voronoi diagram of $\mathcal{P}$ to its Riemannian Voronoi diagram. Both diagrams have dual structures called the discrete Riemannian Delaunay and the Riemannian Delaunay complex. We provide conditions that guarantee that these dual structures are identical. It then follows from previous results that the discrete Riemannian Delaunay complex can be embedded in $\Omega$ under sufficient conditions, leading to an anisotropic triangulation with curved simplices. Furthermore, we show that, under similar conditions, the simplices of this triangulation can be straightened.

We present criteria for establishing a triangulation of a manifold. Given a manifold M, a simplicial complex A, and a map H from the underlying space of A to M, our criteria are presented in local coordinate charts for M, and ensure that H is a homeomorphism. These criteria do not require a differentiable structure, or even an explicit metric on M. No Delaunay property of A is assumed. The result provides a triangulation guarantee for algorithms that construct a simplicial complex by working in local coordinate patches. Because the criteria are easily verified in such a setting, they are expected to be of general use.

In this paper we discuss three results. The first two concern general sets of positive reach: We first characterize the reach by means of a bound on the metric distortion between the distance in the ambient Euclidean space and the set of positive reach. Secondly, we prove that the intersection of a ball with radius less than the reach with the set is geodesically convex, meaning that the shortest path between any two points in the intersection lies itself in the intersection. For our third result we focus on manifolds with positive reach and give a bound on the angle between tangent spaces at two different points in terms of the distance between the points and the reach.

In this article, we focus on the problem of computing Persistent Homology of a flag tower, i.e. a sequence of flag complexes connected by simplicial maps. We show that if we restrict the class of simplicial complexes to flag complexes, we can achieve decisive improvement in terms of time and space complexities with respect to previous work. We show that strong collapses of flag complexes can be computed in time O(k^2v^2) where v is the number of vertices of the complex and k is the maximal degree of its graph. Moreover we can strong collapse a flag complex knowing only its 1-skeleton and the resulting complex is also a flag complex. When we strong collapse the complexes in a flag tower, we obtain a reduced sequence that is also a flag tower we call the core flag tower. We then convert the core flag tower to an equivalent filtration to compute its PH. Here again, we only use the 1-skeletons of the complexes. The resulting method is simple and extremely efficient.

Delaunay has shown that the Delaunay complex of a finite set of points $$P$$ of Euclidean space $$\mathbb {R}^m$$ triangulates the convex hull of $$P,$$ provided that $$P$$ satisfies a mild genericity property. Voronoi diagrams and Delaunay complexes can be defined for arbitrary Riemannian manifolds. However, Delaunay’s genericity assumption no longer guarantees that the Delaunay complex will yield a triangulation; stronger assumptions on $$P$$ are required. A natural one is to assume that $$P$$ is sufficiently dense. Although results in this direction have been claimed, we show that sample density alone is insufficient to ensure that the Delaunay complex triangulates a manifold of dimension greater than 2.

A filtration over a simplicial complex K is an ordering of the simplices of K such that all prefixes in the ordering are subcomplexes of K . Filtrations are at the core of Persistent Homology, a major tool in Topological Data Analysis. To represent the filtration of a simplicial complex, the entire filtration can be appended to any data structure that explicitly stores all the simplices of the complex such as the Hasse diagram or the recently introduced Simplex Tree [Algorithmica’14]. However, with the popularity of various computational methods that need to handle simplicial complexes, and with the rapidly increasing size of the complexes, the task of finding a compact data structure that can still support efficient queries is of great interest. This direction has been recently pursued for the case of maintaining simplicial complexes. For instance, Boissonnat et al. [Algorithmica’17] considered storing the simplices that are maximal with respect to inclusion and Attali et al. [IJCGA’12] considered storing the simplices that block the expansion of the complex. Nevertheless, so far there has been no data structure that compactly stores the filtration of a simplicial complex, while also allowing the efficient implementation of basic operations on the complex. In this article, we propose a new data structure called the Critical Simplex Diagram (CSD), which is a variant of the Simplex Array List [Algorithmica’17]. Our data structure allows one to store in a compact way the filtration of a simplicial complex and allows for the efficient implementation of a large range of basic operations. Moreover, we prove that our data structure is essentially optimal with respect to the requisite storage space. Finally, we show that the CSD representation admits fast construction algorithms for Flag complexes and relaxed Delaunay complexes.

In this paper, we consider variants of the Geometric Subset General Position problem. In defining this problem, a geometric subsystem is specified, like a subsystem of lines, hyperplanes or spheres. The input of the problem is a set of n points in \mathbb{R}^d and a positive integer k. The objective is to find a subset of at least k input points such that this subset is in general position with respect to the specified subsystem. For example, a set of points is in general position with respect to a subsystem of hyperplanes in \mathbb{R}^d if no d+1 points lie on the same hyperplane. In this paper, we study the Hyperplane Subset General Position problem under two parameterizations. When parameterized by k then we exhibit a polynomial kernelization for the problem. When parameterized by h=n-k, or the dual parameter, then we exhibit polynomial kernels which are also tight, under standard complexity theoretic assumptions. We can also exhibit similar kernelization results for d-Polynomial Subset General Position, where a vector space of polynomials of degree at most d are specified as the underlying subsystem such that the size of the basis for this vector space is b. The objective is to find a set of at least k input points, or in the dual delete at most h = n-k points, such that no b+1 points lie on the same polynomial. Notice that this is a generalization of many well-studied geometric variants of the Set Cover problem, such as Circle Subset General Position. We also study general projective variants of these problems. These problems are also related to other geometric problems like Subset Delaunay Triangulation problem.

A filtration over a simplicial complex K is an ordering of the simplices of K such that all prefixes in the ordering are subcomplexes of K. Filtrations are at the core of Persistent Homology, a major tool in Topological Data Analysis. In order to represent the filtration of a simplicial complex, the entire filtration can be appended to any data structure that explicitly stores all the simplices of the complex such as the Hasse diagram or the recently introduced Simplex Tree [Algorithmica ‘14]. However, with the popularity of various computational methods that need to handle simplicial complexes, and with the rapidly increasing size of the complexes, the task of finding a compact data structure that can still support efficient queries is of great interest. This direction has been recently pursued for the case of maintaining simplicial complexes. For instance, Boissonnat et al. [SoCG ‘15] considered storing the simplices that are maximal for the inclusion and Attali et al. [IJCGA ‘12] considered storing the simplices that block the expansion of the complex. Nevertheless, so far there has been no data structure that compactly stores the filtration of a simplicial complex, while also allowing the efficient implementation of basic operations on the complex. In this paper, we propose a new data structure called the Critical Simplex Diagram (CSD) which is a variant of the Simplex Array List (SAL) [SoCG ‘15]. Our data structure allows to store in a compact way the filtration of a simplicial complex, and allows for the efficient implementation of a large range of basic operations. Moreover, we prove that our data structure is essentially optimal with respect to the requisite storage space. Next, we show that the CSD representation admits the following construction algorithms. A new edge-deletion algorithm for the fast construction of Flag complexes, which only depends on the number of critical simplices and the number of vertices. A new matrix-parsing algorithm to quickly construct relaxed Delaunay complexes, depending only on the number of witnesses and the dimension of the complex.

The Simplex Tree (ST) is a recently introduced data structure that can represent abstract simplicial complexes of any dimension and allows efficient implementation of a large range of basic operations on simplicial complexes. In this paper, we show how to optimally compress the Simplex Tree while retaining its functionalities. In addition, we propose two new data structures called Maximal Simplex Tree (MxST) and Simplex Array List (SAL). We analyze the compressed Simplex Tree, the Maximal Simplex Tree, and the Simplex Array List under various settings.

Persistent homology with coefficients in a field $$\mathbb {F}$$ coincides with the same for cohomology because of duality. We propose an implementation of a recently introduced algorithm for persistent cohomology that attaches annotation vectors with the simplices. We separate the representation of the simplicial complex from the representation of the cohomology groups, and introduce a new data structure for maintaining the annotation matrix, which is more compact and reduces substantially the amount of matrix operations. In addition, we propose a heuristic to simplify further the representation of the cohomology groups and improve both time and space complexities. The paper provides a theoretical analysis, as well as a detailed experimental study of our implementation and comparison with state-of-the-art software for persistent homology and cohomology.

Anisotropic meshes are triangulations of a given domain in the plane or in higher dimensions, with elements elongated along prescribed directions. Anisotropic triangulations are known to be well suited for interpolation of functions or solving PDEs. Assuming that the anisotropic shape requirements for mesh elements are given through a metric field varying over the domain, we propose a new approach to anisotropic mesh generation, relying on the notion of anisotropic Delaunay meshes. An anisotropic Delaunay mesh is defined as a mesh in which the star of each vertex $v$ consists of simplices that are Delaunay for the metric associated to vertex $v$. This definition works in any dimension and allows us to define a simple refinement algorithm. The algorithm takes as input a domain and a metric field and provides, after completion, an anisotropic mesh whose elements are sized and shaped according to the metric field.

Anisotropic simplicial meshes are triangulations with elements elongated along prescribed directions. Anisotropic meshes have been shown well suited for interpolation of functions or solving PDEs. They can also significantly enhance the accuracy of a surface representation. Given a surface S endowed with a metric tensor field, we propose a new approach to generate an anisotropic mesh that approximates S with elements shaped according to the metric field. The algorithm relies on the well-established concepts of restricted Delaunay triangulation and Delaunay refinement and comes with theoretical guarantees. The star of each vertex in the output mesh is Delaunay for the metric attached to this vertex. Each facet has a good aspect ratio with respect to the metric specified at any of its vertices. The algorithm is easy to implement. It can mesh various types of surfaces like implicit surfaces, polyhedra, or isosurfaces in 3D images. It can handle complicated geometries and topologies, and very anisotropic metric fields.

CGALmesh is the mesh generation software package of the Computational Geometry Algorithm Library (CGAL). It generates isotropic simplicial meshes—surface triangular meshes or volume tetrahedral meshes—from input surfaces, 3D domains, and 3D multidomains, with or without sharp features. The underlying meshing algorithm relies on restricted Delaunay triangulations to approximate domains and surfaces and on Delaunay refinement to ensure both approximation accuracy and mesh quality. CGALmesh provides guarantees on approximation quality and on the size and shape of the mesh elements. It provides four optional mesh optimization algorithms to further improve the mesh quality. A distinctive property of CGALmesh is its high flexibility with respect to the input domain representation. Such a flexibility is achieved through a careful software design, gathering into a single abstract concept, denoted by the oracle, all required interface features between the meshing engine and the input domain. We already provide oracles for domains defined by polyhedral and implicit surfaces.

We introduce a parametrized notion of genericity for Delaunay triangulations which, in particular, implies that the Delaunay simplices of δ-generic point sets are thick. Equipped with this notion, we study the stability of Delaunay triangulations under perturbations of the metric and of the vertex positions. We then show that, for any sufficiently regular submanifold of Euclidean space, and appropriate ε and δ, any sample set which meets a localized δ-generic ε-dense sampling criteria yields a manifold intrinsic Delaunay complex which is equal to the restricted Delaunay complex.

We consider the problem of reconstructing a compact 3-manifold (with boundary) embedded in ℜ3 from its crosssections with a given set of cutting planes having arbitrary orientations. Under appropriate sampling conditions that are satisfied when the set of cutting planes is dense enough, we prove that the algorithm presented by Liu et al. in [LBD+08] preserves the homotopy type of the original object. Using the homotopy equivalence, we also show that the reconstructed object is homeomorphic (and isotopic) to the original object. This is the first time that shape reconstruction from cross-sections comes with such theoretical guarantees.

We give a provably correct algorithm to reconstruct a k-dimensional manifold embedded in d-dimensional Euclidean space. Input to our algorithm is a point sample coming from an unknown manifold. Our approach is based on two main ideas : the notion of tangential Delaunay complex defined in [6,19,20], and the technique of sliver removal by weighting the sample points [13]. Differently from previous methods, we do not construct any subdivision of the embedding d-dimensional space. As a result, the running time of our algorithm depends only linearly on the extrinsic dimension d while it depends quadratically on the size of the input sample, and exponentially on the intrinsic dimension k. To the best of our knowledge, this is the first certified algorithm for manifold reconstruction whose complexity depends linearly on the ambient dimension. We also prove that for a dense enough sample the output of our algorithm is isotopic to the manifold and a close geometric approximation of the manifold.

We describe a new implementation of the well-known incremental algorithm for constructing Delaunay triangulations in any dimension. Our implementation follows the exact computing paradigm and is fully robust. Extensive comparisons show that our implementation outperforms the best currently available codes for exact convex hulls and Delaunay triangulations, compares very well to the fast non-exact QHull implementation and can be used for quite big input sets in spaces of dimensions up to 6. To circumvent prohibitive memory usage, we also propose a modification of the algorithm that uses and stores only the Delaunay graph (the edges of the full triangulation). We show that a careful implementation of the modified algorithm performs only 6 to 8 times slower than the original algorithm while drastically reducing memory usage in dimension 4 or above.

Abstract Generating realistic geometric models from 3D segmented images is an important task in many biomedical applications. Segmented 3D images impose particular challenges for meshing algorithms because they contain multi‐material junctions forming features such as surface patches, edges and corners. The resulting meshes should preserve these features to ensure the visual quality and the mechanical soundness of the models. We present a feature preserving Delaunay refinement algorithm which can be used to generate high‐quality tetrahedral meshes from segmented images. The idea is to explicitly sample corners and edges from the input image and to constrain the Delaunay refinement algorithm to preserve these features in addition to the surface patches. Our experimental results on segmented medical images have shown that, within a few seconds, the algorithm outputs a tetrahedral mesh in which each material is represented as a consistent submesh without gaps and overlaps. The optimization property of the Delaunay triangulation makes these meshes suitable for the purpose of realistic visualization or finite element simulations.

Various definitions of so called anisotropic Voronoi diagrams have been proposed. These diagrams are typically parameterized by a metric field. Under mild hypotheses on the metric field, such Voronoi diagrams can be refined so that their dual is a triangulation, with elements shaped according to the specified anisotropic metric field. We propose an alternative approach to anisotropic mesh generation, relying on the notion of locally uniform anisotropic mesh. A locally uniform anisotropic mesh is a mesh such that the star around each vertex v coincides with the star that v would have if the metric on the domain was uniform and equal to the metric at v. This definition allows to define a simple refinement algorithm which relies on elementary predicates, and provides, after completion, an anisotropic mesh in dimensions 2 and 3.

Abstract This paper deals with the reconstruction of 2‐dimensional geometric shapes from unorganized 1‐dimensional cross‐sections. We study the problem in its full generality following the approach of Boissonnat and Memari [ BM07 ] for the analogous 3D problem. We propose a new variant of this method and provide sampling conditions to guarantee that the output of the algorithm has the same topology as the original object and is close to it (for the Hausdorff distance).

It is a well-established fact that the witness complex is closelyrelated to the restricted Delaunay triangulation in lowdimensions. Specifically, it has been proved that the witness complexcoincides with the restricted Delaunay triangulation on curves, and isstill a subset of it on surfaces, under mild samplingassumptions. Unfortunately, these results do not extend tohigher-dimensional manifolds, even under stronger samplingconditions. In this paper, we show how the sets of witnesses andlandmarks can be enriched, so that the nice relations that existbetween both complexes still hold on higher-dimensional manifolds. Wealso use our structural results to devise an algorithm thatreconstructs manifolds of any arbitrary dimension or co-dimension atdifferent scales. The algorithm combines a farthest-point refinementscheme with a vertex pumping strategy. It is very simple conceptually,and it does not require the input point sample W to be sparse. Itstime complexity is bounded by c(d) |W|2, where c(d) is a constantdepending solely on the dimension d of the ambient space.

Voronoi diagrams are fundamental geometric structures that partition the space into elementary regions of influence defining discrete proximity graphs and dually well-shaped Delaunay triangulations [Aurenhammer & Klein, 2000]. In this video, we explain and illustrate a recent generalization of Voronoi diagrams [Nielsen et al., 2007] to a wide class of distortion measures called Bregman divergences [Banerjee et al., 2005].

In this paper, we propose a robust and efficient Lagrangian approach, which we call Delaunay deformable models, for modeling moving surfaces undergoing large deformations and topology changes. Our work uses the concept of restricted Delaunay triangulation, borrowed from computational geometry. In our approach, the interface is represented by a triangular mesh embedded in the Delaunay tetrahedralization of interface points. The mesh is iteratively updated by computing the restricted Delaunay triangulation of the deformed objects. Our method has many advantages over popular Eulerian techniques such as the level set method and over hybrid Eulerian-Lagrangian techniques such as the particle level set method: localization accuracy, adaptive resolution, ability to track properties associated to the interface, seamless handling of triple junctions. Our work brings a rigorous and efficient alternative to existing topology-adaptive mesh techniques such as T-snakes.

Abstract In this paper, we propose a robust and efficient Lagrangian approach for modeling dynamic interfaces between different materials undergoing large deformations and topology changes, in two dimensions. Our work brings an interesting alternative to popular techniques such as the level set method and the particle level set method, for two‐dimensional and axisymmetric simulations. The principle of our approach is to maintain a two‐dimensional triangulation which embeds the one‐dimensional polygonal description of the interfaces. Topology changes can then be detected as inversions of the faces of this triangulation. Each triangular face is labeled with the type of material it contains. The connectivity of the triangulation and the labels of the faces are updated consistently during deformation, within a neat framework developed in computational geometry: kinetic data structures. Thanks to the exact computation paradigm, the reliability of our algorithm, even in difficult situations such as shocks and topology changes, can be certified. We demonstrate the applicability and the efficiency of our approach with a series of numerical experiments in two dimensions. Finally, we discuss the feasibility of an extension to three dimensions.

In the last decade, a great deal of work has been devoted to the elaboration of a sampling theory for smooth surfaces. The goal was to ensure a good reconstruction of a given surface S from a finite subset E of S. The sampling conditions proposed so far offer guarantees provided that E is sufficiently dense with respect to the local feature size of S, which can be true only if S is smooth since the local feature size vanishes at singular points.In this paper, we introduce a new measurable quantity, called the Lipschitz radius, which plays a role similar to that of the local feature size in the smooth setting, but which is well-defined and positive on a much larger class of shapes. Specifically, it characterizes the class of Lipschitz surfaces, which includes in particular all piecewise smooth surfaces such that the normal deviation is not too large around singular points.Our main result is that, if S is a Lipschitz surface and E is a sample of S such that any point of S is at distance less than a fraction of the Lipschitz radius of S, then we obtain similar guarantees as in the smooth setting. More precisely, we show that the Delaunay triangulation of E restricted to S is a 2-manifold isotopic to S lying at bounded Hausdorff distance from S, provided that its facets are not too skinny.We further extend this result to the case of loose samples. As an application, the Delaunay refinement algorithm we proved correct for smooth surfaces works as well and comes with similar guarantees when applied to Lipschitz surfaces.

The input pupil of interferometry-based observation instruments is necessarily segmented. Since the Optical Transfer Function (OTF) of any optical instrument observing in incoherent light is the auto-correlation of its input pupil, it follows that any combination of size and position of each pupil segment will have an impact on the OTF behavior and therefore on the quality of the output image. The goal of this study is to propose computational geometry methods allowing to find pupil geometries leading to an isotropic OTF support with a controlled redundancy of viewed spatial frequencies in the Fourier domain.

We consider the problem of discovering a smooth unknown surface S bounding an object O in R3. The discovery process consists of moving a point probing device in the free space around O so that it repeatedly comes in contact with S. We propose a probing strategy for generating a sequence of surface samples on S from which a triangulated surface can be generated which approximates S within any desired accuracy. We bound the number of probes and the number of elementary moves of the probing device. Our solution is an extension of previous work on Delaunay refinement techniques for surface meshing. The approximating surface we generate enjoys the many nice properties of the meshes obtained by those techniques, e.g. exact topological type, normal approximation, etc.

This paper addresses the problem of piecewise linear approximation of implicit surfaces. We first give a criterion ensuring that the zero-set of a smooth function and the one of a piecewise linear approximation of it are isotopic. Then, we deduce from this criterion an implicit surface meshing algorithm certifying that the output mesh is isotopic to the actual implicit surface. This is the first algorithm achieving this goal in a provably correct way.

It is well known that the complexity of the Delaunay triangulation of N points in R 3, i.e. the number of its faces, can be O (N2). 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 generic smooth surfaces of R 3. Under a mild uniform sampling condition, we show that the complexity of the 3D Delaunay triangulation of the points is O(N log N).

Let PC be a 3D point cloud and ε be a positive value called tolerance. We aim at constructing a triangulated surface S based on a subset PCU of PC such that all the points in PCL=PC∖PCU are at distance at most ε from a facet of S. (PCU and PCL respectively stand for Point Cloud Used and Point Cloud Left.) We call this problem simplification with geometric guarantees. This paper presents a new framework to simplify with geometric guarantees. The approach relies on two main ingredients. First an oracle providing information on the surface being reconstructed even though the triangulated surface itself has not been computed. Second, a reconstruction algorithm providing incremental updates of the reconstructed surface, as well as a fast point-to-triangles distance computation. The oracle is used to guess a subset of the point cloud from which a triangulated surface is reconstructed. It relies on an implicit surface the triangulated surface is an approximation of, and is therefore available before the triangle mesh. The point-to-triangles distance computation and the local updates are then invoked to insert new vertices until the tolerance is met. We also present a detailed experimental study which shows the efficiency of the simplification process both in terms of simplification rate and running time. To the best of our knowledge, this algorithm is the first one performing coarse-to-fine surface simplification with geometric guarantees.

We present an algorithm to reconstruct smooth surfaces of arbitrary topology from unorganised sample points and normals. The method uses natural neighbour interpolation, works in any dimension and allows to deal with non uniform samples. The reconstructed surface is a smooth manifold passing through all the sample points. This surface is implicitly represented as the zero-set of some pseudo-distance function. It can be meshed so as to satisfy a user-defined error bound. Experimental results are presented for surfaces in R^3.

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

We study the problem of computing the free space ${\cal F}$ of a simple legged robot called the spider robot. The body of this robot is a single point and the legs are attached to the body. The robot is subject to two constraints: each leg has a maximal extension R (accessibility constraint) and the body of the robot must lie above the convex hull of its feet (stability constraint). Moreover, the robot can only put its feet on some regions, called the foothold regions. The free space ${\mathcal{F}}$ is the set of positions of the body of the robot such that there exists a set of accessible footholds for which the robot is stable. We present an efficient algorithm that computes ${\cal F}$ in $O(n^2\log n)$ time using $O(n^2\alpha(n))$ space for n discrete point footholds where $\alpha(n)$ is an extremely slowly growing function ($\alpha(n)\leq 3$ for any practical value of n). We also present an algorithm for computing ${\cal F}$ when the foothold regions are pairwise disjoint polygons with n edges in total. This algorithm computes ${\cal F}$ in $O(n^2\alpha_8(n)\log n)$ time using $O(n^2\alpha_8(n))$ space. ($\alpha_8(n)$ is also an extremely slowly growing function.) These results are close to optimal since $\Omega(n^2)$ is a lower bound for the size of ${\cal F}$.

In this paper, we reexamine in the framework of robust computation the Bentley--Ottmann algorithm for reporting intersecting pairs of segments in the plane. This algorithm has been reported as being very sensitive to numerical errors. Indeed, a simple analysis reveals that it involves predicates of degree 5, presumably never evaluated exactly in most implementations. Within the exact-computation paradigm we introduce two models of computation aimed at replacing the conventional model of real-number arithmetic. The first model (predicate arithmetic) assumes the exact evaluation of the signs of algebraic expressions of some degree, and the second model (exact arithmetic) assumes the exact computation of the value of such (bounded-degree) expressions. We identify the characteristic geometric property enabling the correct report of all intersections by plane sweeps. Verification of this property involves only predicates of (optimal) degree 2, but its straightforward implementation appears highly inefficient. We then present algorithmic variants that have low degree under these models and achieve the same performance as the original Bentley--Ottmann algorithm. The technique is applicable to a more general case of curved segments.

No abstract available.

IntroductionWe consider whether restricted sets of geometric predicates support efficient algorithms to solve line and curve segment intersection problems in the plane.Our restrictions are based on the notion of algebraic degree, proposed by Preparata and others as a way to guide the search for efficient algorithms that can be implemented in more realistic computational models than the Real RAM.Suppose that n (pseudo-)segments have k intersections at which they cross.We show that intersection algorithms for monotone curves that use only comparisons and above/below tests for endpoints, and intersection tests, must take at least Q(n&) time.There are optimal O(n log n + k) algorithms that use a higher-degree test comparing x coordinates of an endpoint and intersection point; for line segments we show that this test can be simulated using CCW() tests with a logarithmic loss of efficiency.We also give an optimal 0( n log n + k) algorithms for red/blue line and curve segment intersection, in which the segments are colored red and blue so that there are no red/red or blue/blue crossings.

Satellite layout is a very hard tw.k because avail- able space for the equipments is small and the physical constraints on the layout are strong.In this article, we show how some physical layout constraints can be modeled geometrically and how Minkowsk] operations can be used to place equipments, and in particular antennas.Since antennas are supposed to be placed onto a satellite wall, search space is two-dimensional.We discuss an algorithm that efficiently calculates only the (planar) part we need of the admissible space and deecribe how we implemented this.

In this paper, we consider the problem of computing a shortest path of bounded curvature amidst obstacles in the plane. More precisely, given prescribed initial and nal congurations (i.e. positions and orientations) and a set of obstacles in the plane, we want to compute a shortest C 1 path joining those two congurations, avoiding the obstacles, and with the further constraint that, on each C 2 piece, the radius of curvature is at least 1. In this paper, we consider the case of moderate obstacles (as introduced by Agarwal et al. [1]) and present a polynomial-time exact algorithm to solve this problem. 1 Introduction In this paper, we consider the problem of computing a shortest path of bounded curvature amidst obstacles in the plane, SBC path for short. More precisely, given prescribed initial and nal congurations (i.e. positions and orientations) and a set of obstacles in the plane, we want to compute a shortest C 1 path joining those two congurations, avoiding the obstacles,...

No abstract available.

No abstract available.

The paper bounds the combinatorial complexity of the Voronoi diagram of a set of points under certain polyhedral distance functions.Specifically, if S is a set of n points in general position in Jf?-d, the complexity of its Voronoi diagram under the Lm metric, and also under a simplicial distance function, are both shown to be qn[dlzl ).The upper bound for the case of the Lm metric folIows from a new upper bound, also proved in this paper, on the complexity of the union of n axis-parallel hypercubes in Eld.This complexity is @(n ~d/21 ), for d > 1, and it improves to @(nld/2J ), for d ~2, if all the hypercubes have the same size.Under the L1 metric, the complexity of the Voronoi diagram of a set of n points in general position in IR3 is shown to be @(n2 ).We also show that the general position assumption is essential, and give examples where the complexity of the diagram increases significantly when the points are in degenerate configurations.

Studies the problem of computing the set F of accessible and stable placements of a spider robot. The body of this robot is a single point and the legs are line segments attached to the body. The robot can only put its feet on some regions, called the foothold regions. Moreover, the robot is subject to two constraints: each leg has a maximal extension R (accessibility constraint) and the body of the robot must lie above the convex hull of its feet (stability constraint). The authors present an efficient algorithm to compute F. If the foothold regions are polygons with n edges in total, the authors' algorithm computes F in O(n/sup 2/ log n) time and O(n/sup 2//spl alpha/(n)) space where /spl alpha/ is the inverse of Ackerman's function. /spl Omega/(n/sup 2/) is a lower bound for the size of F.>

We calculate the partition of the configuration space R/sup 2//spl times/S/sup 1/ of a car-like robot, only moving forwards, with respect to the type of the length optimal paths. This kind of robot is subject to kinematic constraints on its path curvature and its orientation. Starting from the results on shortest paths, we give new optimality conditions on these paths, and compute the partition for any horizontal plane of the configuration space.>

We show how to create 3D models of maternal pelvis and fetal head from magnetic resonance images (MRI). The models are used to simulate the progress of delivery in order to give a prognosis of successful labor.>

We study the problem of computing the set of admissible and stable placements of spider robots, a simple case of legged robots. The environment consists of a set of n points in the plane representing authorized footholds. We show that the space of admissible and stable placements of such robots has size θ(n2) and can be constructed in O(n2 log n) time and O(n2) space. We give also efficient algorithms for several related problems.

Given two oriented points in the plane, the authors determine and compute the shortest paths of bounded curvature joining them. This problem has been solved by L.E. Dubins (1957) in the no-cusp case, and by J.A. Reeds and L.A. Shepp (1990) with cusps. A solution based on the minimum principle of Pontryagin is proposed. The approach simplifies the proofs and makes clear the global or local nature of the results. The no-cusp case and the more difficult case with cusps are discussed.>

The authors consider a simple instance of the problem of planning motions of legged robots. The robot is modeled as a point where all its legs are attached, and the footholds where the robot can securely place its feet consist of a set of points in the plane. Efficient algorithms to compute stable motions in such situations are presented.>

We show, in this paper, how one can probe a class of non convex polyhedra and scenes of disjoint such polyhedra. A polyhedron of that class has convex faces; any two faces are not coplanar and any two edges are not colinear. The basic step of our method is a strategy for probing a single simple polygon with no colinear edges. When each probe outcome consists of a contact point and the normal to the object at the point, we present a strategy that discovers the exact shape of a simple polygon with no colinear edges by means of at most 3n - 3 probes, which is shown to be optimal in the worst-case. This strategy can be extended to probe a family of disjoint polygons. It can also be applied in the supporting planes of the faces of a scene of polyhedra of the class above. If the scene consists of k polyhedra with altogether n faces, we show that 8n2 - 6n + k probes are sufficient to discover the exact shapes of the polyhedra.

The authors present a strategy for discovering the exact shape of a simple (but not necessarily convex) polygon by means of a minimal number of simple probes. When each probe outcome consists of a contact point, a ray measuring that point and the normal to the object at the point, it is shown that 3n-3 probes are necessary and sufficient to discover the exact shape of a polygon with n noncollinear edges. Each probe can be determined in O(log n) time, yielding on O(n log n)-time O(n)-space algorithm.>

This article proposes a coherent method of interpolating 3D data obtained for example by stereo, with a polyhedral surface by means of the Delaunay Triangulation. We first give some theoretical properties concerning the approximations of sampled objects we obtain when the sampling rate increases, based on the study of their skeleton using some tools of Mathematical Morphology. Then, we present the algorithms and their complexity analysis which yield both a surface representation of objects and a volume representation of free space which may be useful in Robotics. This goal is achieved by means of a simple visibility criterion. The method is intrinsically discontinuity preserving and can be used for the integration of multiple viewpoints.

An exact solution is presented to the following inspection problem in two dimensions. A manufactured part is desired to have a polygonal shape E/sub d/. Tolerances are given in terms of two polygons, one, called E/sup -/ lying within E/sub d/, and the other, called E/sup +/, lying outside E/sub d/. A vision system yields a description of each manufactured part as a polygon I. It is desired to determine whether I can be translated and rotated to lie between the tolerance polygons E/sup -/ and E/sup +/, in which case the part is considered to conform to the desired tolerances.>

A general and simple algorithm is presented which computes the set FP of all free configurations for a polygonal object I (with m edges) which is free to translate and/or to rotate but not to intersect another polygonal object E. The worst-case time complexity of the algorithm is O(m/sup 3/n/sup 3/ log mn), which is close to optimal. FP is a three-dimensional curved object which can be used to find free motions within the same time bounds. Two types of motion have been studied in some detail. Motion in contact, where I remains in contact with E, is performed by moving along the faces of the boundary of FP. By partitioning FP into prisms, it is possible to compute motions when I never makes contact with E. In this case, the theoretical complexity does not exceed O(m/sup 6/n/sup 6/ alpha (mn)) but it is expected to be much smaller in practice. In both cases, pseudo-optimal motions can be obtained with a complexity increased by a factor log mn.>

A coherent way of interpolating 3-D data obtained by stereo, for example, with a simplicial polyhedral surface is discussed. The method is based on constrained Delaunay triangulation; the polyhedral surface is obtained by using a simple visibility property to mark tetrahedra likely to be empty. The method is intrinsically discontinuity-preserving and yields both a surface representation of objects and a volume representation of free space which may be useful in robotics. Algorithms to implement the method are described and their complexity analyzed in the worst case and average case situations where tools of probabilistic geometry are used.>

The problem of reconstructing shapes of objects from sparse measurements such as points on the boundary of an object is considered. In most situations, the points are the endpoints of a curve or a ray which does not cross the objects. For example, if the sensor is an optical device, the ray is the straight line (the optical ray) joining the camera center to the point. It is shown that the information provided by rays is crucial when determining the shapes of objects, and nonheuristic reconstruction methods in 2-D and 3-D space are described. An efficient method is derived for the reconstruction of surfaces from 3-D segments provided by a stereo vision process.>

We present an optimal algorithm to reconstruct the planar cross section of a simple object from data points measured by rays. The rays are semi-infinite curves representing, for example, the laser beam or the articulated arms of a robot moving around the object. The object is assumed to be a unique simply connected object, and the contour to be reconstructed is a simple polygon having the data points as vertices and intersecting none of the measuring rays. Such a contour does not exist for any given sets of points and rays but only for legal data. In this paper, we prove that the solution to the contour problem is unique whenever such a solution exists. For a set of n points and n rays, the algorithm presented here provides in Ο(nlogn) time, a polygon which is the solution to the contour problem when the data are legal. Updating this contour if a new measure is available can be done in Ο(logn) time. Both results are asymptotically optimal in the worst-case. Moreover, once the solution has been found, we can check if the data are legal in Ο(nlogn) time.

Article Free Access Share on Simultaneous containment of several polygons Authors: F. Avnaim INRIA, Avenue Emile Hugues, 06565 VALBONNE INRIA, Avenue Emile Hugues, 06565 VALBONNEView Profile , J. Bsissonnat INRIA, Avenue Emile Hugues, 06565 VALBONNE INRIA, Avenue Emile Hugues, 06565 VALBONNEView Profile Authors Info & Claims SCG '87: Proceedings of the third annual symposium on Computational geometryOctober 1987 Pages 242–247https://doi.org/10.1145/41958.41984Published:01 October 1987Publication History 21citation325DownloadsMetricsTotal Citations21Total Downloads325Last 12 Months7Last 6 weeks2 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

We present, in this paper, a new hierarchical data structure called the Delaunay tree. It is defined from the Delaunay triangulation and, roughly speaking, represents a triangulation as a hierarchy of balls. The Delaunay tree provides efficient solutions to several problems such as building the Delaunay triangulation of a finite set of n points in any dimension, locating a point in the triangulation, defining neighborhood relationships in the triangulation and computing intersections. The algorithms are extremely simple and are analyzed from a theoretical and practical points of view.

Different geometric structures are investigated in the context of discrete surface representation.It is shown that minimal representations (i.e., polyhedra) can be provided by a surface-based method using nearest neighbors structures or by a volume-based method using the Delaunay triangulation.Both approaches are compared with respect to various criteria, such as space requirements, computation time, constraints on the distribution of the points, facilities for further calculations, and agreement with the actual shape of the object.

A method is proposed which determines the possible ways to grasp an object, defined by its silhouette. This method is quite general and versatile: the geometry of the object is arbitrary and a large class of grippers is allowed; no a priori information is needed, except the parameters of the gripper, and so the method applies, in particular, to all the automatic prehension problems when the object and/or its orientation are unknown. Suitable segmentation and parametrization of the silhouette yields an explicit solution and a very fast and simple algorithm.