Abstract Motivated by recent work on Delaunay triangulations of hyperbolic surfaces, we consider the minimal number of vertices of such triangulations. First, we show that every hyperbolic surface of genus g has a simplicial Delaunay triangulation with O(g) vertices, where edges are given by distance paths. Then, we construct a class of hyperbolic surfaces for which the order of this bound is optimal. Finally, to give a general lower bound, we show that the $$\Omega (\sqrt{g})$$ Ω ( g ) lower bound for the number of vertices of a simplicial triangulation of a topological surface of genus g is tight for hyperbolic surfaces as well.

Earlier work on Delaunay triangulation of point sets on the 2D flat torus, which is locally isometric to the Euclidean plane, was based on lifting the point set to a locally isometric 9-sheeted covering space of the torus. Under mild conditions the Delaunay triangulation of the lifted point set, consisting of 9 copies of the input set, projects to the Delaunay triangulation of the input set. We improve and generalize this work. First we present a new construction based on an 8-sheeted covering space, which shows that eight copies suffice for the standard flat torus. Then we generalize this construction to the context of compact orientable surfaces of higher genus, which are locally isometric to the hyperbolic plane. We investigate more thoroughly the Bolza surface, homeomorphic to a sphere with two handles, both because it is the hyperbolic surface with lowest genus, and because triangulations on the Bolza surface have applications in various fields such as neuromathematics and cosmological models. While the general properties (existence results of appropriate covering spaces) show similarities with the results for the flat case, explicit constructions and their proofs are much more complex, even in the case of the apparently simple Bolza surface. One of the main reasons is the fact that two hyperbolic translations do not commute in general. To the best of our knowledge, the results in this paper are the first ones of this kind. The interest of our contribution lies not only in the results, but most of all in the construction of covering spaces itself and the study of their properties.

We study a natural intrinsic definition of geometric simplices in Riemannian manifolds of arbitrary finite dimension, and exploit these simplices to obtain criteria for triangulating compact Riemannian manifolds. These geometric simplices are defined using Karcher means. Given a finite set of vertices in a convex set on the manifold, the point that minimises the weighted sum of squared distances to the vertices is the Karcher mean relative to the weights. Using barycentric coordinates as the weights, we obtain a smooth map from the standard Euclidean simplex to the manifold. A Riemannian simplex is defined as the image of the standard simplex under this barycentric coordinate map. In this work we articulate criteria that guarantee that the barycentric coordinate map is a smooth embedding. If it is not, we say the Riemannian simplex is degenerate. Quality measures for the "thickness" or "fatness" of Euclidean simplices can be adapted to apply to these Riemannian simplices. For manifolds of dimension 2, the simplex is non-degenerate if it has a positive quality measure, as in the Euclidean case. However, when the dimension is greater than two, non-degeneracy can be guaranteed only when the quality exceeds a positive bound that depends on the size of the simplex and local bounds on the absolute values of the sectional curvatures of the manifold. An analysis of the geometry of non-degenerate Riemannian simplices leads to conditions which guarantee that a simplicial complex is homeomorphic to the manifold.

In this video we highlight the application of Computational Geometry to our understanding of the formation and dynamics of the Cosmic Web. The emergence of this intricate and pervasive weblike structure of the Universe on Megaparsec scales can be approximated by a well-known equation from fluid mechanics, the Burgers' equation. The solution to this equation can be obtained from a geometrical formalism. We have extended and improved this method by invoking weighted Delaunay and Voronoi tessellations. The duality between these tessellations finds a remarkable and profound reflection in the description of physical systems in Eulerian and Lagrangian terms.

The Morse-Smale complex is an important tool for global topological analysis in various problems of computational geometry and topology. Algorithms for Morse-Smale complexes have been presented in case of piecewise linear manifolds. However, previous research in this field does not provide certified methods in the case of smooth functions. In the current paper we use interval arithmetic to compute a topologically correct approximation of Morse-Smale complex of smooth functions of two variables. The algorithm can also compute geometrically close Morse-Smale complex.

Abstract For a surface in 3‐space that is represented by a set S of sample points, we construct a coarse approximating polytope P that uses a subset of S as its vertices and preserves the topology of . In contrast to surface reconstruction we do not use all the sample points, but we try to use as few points as possible. Such a polytope P is useful as a ‘seed polytope’ for starting an incremental refinement procedure to generate better and better approximations of based on interpolating subdivision surfaces or e.g. Bézier patches. Our algorithm starts from an r‐sample S of . Based on S, a set of surface covering balls with maximal radii is calculated such that the topology is retained. From the weighted α‐shape of a proper subset of these highly overlapping surface balls we get the desired polytope. As there is a rather large range for the possible radii for the surface balls, the method can be used to construct triangular surfaces from point clouds in a scalable manner. We also briefly sketch how to combine parts of our algorithm with existing medial axis algorithms for balls, in order to compute stable medial axis approximations with scalable level of detail.

Level sets are isosurfaces of an implicit function F: R3rarr R K, that is the set of points satisfying F(x,y,z) = 0.In this paper we introduce an algorithm to move at interactive speed through the different level sets. Furthermore the meshes of the level sets are isotopic to the isosurface itself, as long as the surface stays away from singularities. When the surface moves close to singularities, the algorithm indicates arbitrarily small boxes where the topology is not certified. In this case, the user can decide to decrease the size of the boxes by further refinement. For special classes of functions, such as algebraic surfaces, other methods could be used to determine the topology inside the singular boxes.

We construct a class of envelope surfaces in Rd, more precisely envelopes of balls. An envelope surface is a closed C1 (tangent continuous) manifold wrapping tightly around the union of a set of balls. Such a manifold is useful in modeling since the union of a finite set of balls can approximate any closed smooth manifold arbitrarily close.The theory of envelope surfaces generalizes the theoretical framework of skin surfaces [5] developed by Edelsbrunner for molecular modeling. However, envelope surfaces are more flexible: where a skin surface is controlled by a single parameter, envelope surfaces can be adapted locally.We show that a special subset of envelope surfaces is piecewise quadratic and derive conditions under which the envelope surface is C1. These conditions can be verified automatically. We give examples of envelope surfaces to demonstrate their flexibility in surface design.

The contour generator is an important visibility feature of a smooth object seen under parallel projection. It is the curve on the surface which seperates front-facing from back-facing regions. The apparent contour is the projection of the contour generator onto a plane perpendicular to the view direction. Both curves play an important role in computer graphics.Our goal is to obtain fast and robust algorithms that compute the contour generator with a guarantee of topological correctness. To this end, we first study the singularities of the contour generator and apparent contour for both generic views and generic time-dependent projections, for example, when the surface is rotated or deformed. The singularities indicate when components of the contour generator merge or split as time evolves.We present an algorithm to compute an initial contour generator by using a dynamic step size. An interval test guarantees the topological correctness. This initial contour generator can thus be maintained under a time-dependent projection by examining its singularities.

Skin surfaces are used for the modeling and visualization of molecules. They form a class of tangent continuous surfaces defined in terms of a set of balls (the atoms of the molecule) and a shrink factor. More recently, skin surfaces have been used to approximate arbitrary surfaces. We present an algorithm that approximates a skin surface with a topologically correct mesh. The complexity of the mesh is linear in the size of the Delaunay triangulation of the balls, which is worst case optimal. We also adapt two existing refinement algorithms to improve the quality of the mesh and show that the same algorithm can be used for meshing a union of balls.

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.

A closed orientable surface of genus $g$ can be obtained by appropriat e identification of pairs of edges of a $4g$-gon (the polygonal schema). The identified edges form $2g$ loops on the surface, that are disjoint except for their common end-point. These loops are generators of both the fundamental group and the homology group of the surface. The inverse problem is concerned with finding a set of $2g$ loops on a triangulated surface, such that cutting the surface along these loops yields a (canonical) polygonal schema. We present two optimal algorithms for this inverse problem. Both algorithms have been implemented using the CGAL polyhedron data structure.

We show that the k free bitangents of a collection of n pairwise disjoint convex plane sets can be computed in time O(k+n log n) and O(n) working space. The algorithm uses only one advanced data structure, namely a splittable queue. We introduce (weakly) greedy pseudo--triangulations, whose combinatorial properties are crucial for our method. 1 Introduction Consider a collection O of pairwise disjoint convex objects in the plane. We are interested in problems in which these objects arise as obstacles, either in connection with visibility problems where they can block the view from an other geometric object, or in motion planning, where these objects may prevent a moving object from moving along a straight line path. The visibility graph is a central object in such contexts. For polygonal obstacles the vertices of these polygons are the nodes of the visibility graph, and two nodes are connected by an arc if the corresponding vertices can see each other. [9] describes the first non-triv...

We introduce the visibility complex of a collection O of n pairwise disjoint convex objects in the plane. This 2 dimensional cell complex may be considered as a generalization of the tangent visibility graph of 0. Its space complexity k is proportional to the size of the tangent visibility graph. We give an O(nlog n+k) algorithm for its construction. Furthermore we show how the visibility complex can be used to compute the view from a point or a convex object with respect to O in O(m log n) time, where m is the size of the view. The view from a point is a generalization of the visibility polygon of that point with respect to O.

We investigate the computational problems associated with combinatorial surfaces. Specifically, we present an algorithm (based on the Brahana-Dehn-Heegaard approach) for transforming the polygonal schema of a closed triangulated surface into its canonical form in Ο(n log n) time, where n is the total number of vertices, edges and faces. We also give an Ο(n log n + gn) algorithm for constructing canonical generators of the fundamental group of a surface of genus g. This is useful in constructing homeomorphisms between combinatorial surfaces.

We consider a discrete version of the Whitney-Graustein theorem concerning regular equivalence of closed curves. Two regular polygons P and P', i.e. polygons without overlapping adjacent edges, are called regularly equivalent if there is a continuous one-parameter family Ps, O ≥ s ≤ 1 of regular polygons with Po = P and P1 = P'. Geometrically the one-parameter family is a kink-free deformation transforming P into P'. The winding number of a polygon is a complete invariant of its regular equivalence class. We develop a linear algorithm that determines a linear number of elementary steps to deform a regular polygon into any other regular polygon with the same winding number.