Abstract The Delaunay triangulation of a set of points P on a hyperbolic surface is the projection of the Delaunay triangulation of the set $$\widetilde{P}$$ P ~ of lifted points in the hyperbolic plane. Since $$\widetilde{P}$$ P ~ is infinite, the algorithms to compute Delaunay triangulations in the plane do not generalize naturally. Using a Dirichlet domain, we exhibit a finite set of points that captures the full triangulation. We prove that an edge of a Delaunay triangulation has a combinatorial length (a notion we define in the paper) smaller than $$12g-6$$ 12 g - 6 with respect to a Dirichlet domain. To achieve this, we introduce new tools, of intrinsic interest, that capture the properties of length-minimizing curves in the context of closed curves. We then use these to derive structural results on Delaunay triangulations and exhibit certain distance minimizing properties of both the edges of a Delaunay triangulation and of a Dirichlet domain. The bounds produced in this paper depend only on the topology of the surface. They provide mathematical foundations for hyperbolic analogs of the algorithms to compute periodic Delaunay triangulations in Euclidean space.

The goal of this paper is to exhibit and analyze an algorithm that takes a given closed orientable hyperbolic surface and outputs an explicit Dirichlet domain. The input is a fundamental polygon with side pairings. While grounded in topological considerations, the algorithm makes key use of the geometry of the surface. We introduce data structures that reflect this interplay between geometry and topology and show that the algorithm finishes in polynomial time, in terms of the initial perimeter and the genus of the surface.

Even though Delaunay originally introduced his famous triangulations in the case of infinite point sets with translational periodicity, a software that computes such triangulations in the general case is not yet available, to the best of our knowledge. Combining and generalizing previous work, we present a practical algorithm for computing such triangulations. The algorithm has been implemented and experiments show that its performance is as good as the one of the CGAL package, which is restricted to cubic periodicity.

In most layered additive manufacturing processes, a tool solidifies or deposits material while following pre-planned trajectories to form solid beads. Many interesting problems arise in this context, among which one concerns the planning of trajectories for filling a planar shape as densely as possible. This is the problem we tackle in the present paper. Recent works have shown that allowing the bead width to vary along the trajectories helps increase the filling density. We present a novel technique that, given a deposition width range, constructs a set of closed beads whose width varies within the prescribed range and fill the input shape. The technique outperforms the state of the art in important metrics: filling density (while still guaranteeing the absence of bead overlap) and trajectories smoothness. We give a detailed geometric description of our algorithm, explore its behavior on example inputs and provide a statistical comparison with the state of the art. We show that it is possible to obtain high quality fabricated layers on commodity FDM printers.

The CGAL library offers software packages to compute Delaunay triangulations of the (flat) torus of genus one in two and three dimensions. To the best of our knowledge, there is no available software for the simplest possible extension, i.e., the Bolza surface, a hyperbolic manifold homeomorphic to a torus of genus two. In this paper, we present an implementation based on the theoretical results and the incremental algorithm proposed last year at SoCG by Bogdanov, Teillaud, and Vegter. We describe the representation of the triangulation, we detail the different steps of the algorithm, we study predicates, and report experimental results.

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.

In a classical Symbolic Perturbation scheme, degeneracies are handled by substituting some polynomials in epsilon for the inputs of a predicate. Instead of a single perturbation, we propose to use a sequence of (simpler) perturbations. Moreover, we look at their effects geometrically instead of algebraically; this allows us to tackle cases that were not tractable with the classical algebraic approach.

We study Delaunay complexes and Voronoi diagrams in the Poincaré ball, a conformal model of the hyperbolic space, in any dimension. We elaborate on our earlier work on the space of spheres [CCCG'92], giving a detailed description of algorithms. We also study algebraic and arithmetic issues, observing that only rational computations are needed. All proofs are based on geometric reasoning, they do not resort to any use of the analytic formula of the hyperbolic distance. This allows for an exact and efficient implementation in 2D. All degenerate cases are handled. The implementation will be submitted to the CGAL editorial board for future integration into the CGAL library.

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.

International audience

The Computational Geometry Algorithms Library Cgal currently provides packages to compute triangulations in ℝ2 and ℝ3. In this paper we describe a new design for the 3D triangulation package that permits to easily add functionality to compute triangulations in other spaces. These design changes have been implemented, and validated on the case of the periodic space T3. We give a detailed description of the realized changes together with their motivation. Finally, we show benchmarks to prove that the new design does not affect the efficiency.

In this video, we first review the incremental algorithm to compute Delaunay triangulations in R3. Then we examine the case of the periodic space T3, focusing on the differences with R3.

This article introduces the absolute quadratic complex formed by all lines that intersect the absolute conic. If /spl omega/ denotes the 3 /spl times/ 3 symmetric matrix representing the image of that conic under the action of a camera with projection matrix P, it is shown that /spl omega/ /spl ap/ P/sup ~//spl Omega//sub /spl I.bar//P/sup ~T/ where V is the 3 /spl times/ 6 line projection matrix associated with P and /spl Omega//sub /spl I.bar// is a 6 /spl times/ 6 symmetric matrix of rank 3 representing the absolute quadratic complex. This simple relation between a camera's intrinsic parameters, its projection matrix expressed in a projective coordinate frame, and the metric upgrade separating this frame from a metric one - as respectively captured by the matrices /spl omega/, P/sup ~/ and /spl Omega//sub /spl I.bar// - provides a new framework for autocalibration, particularly well suited to typical digital cameras with rectangular or square pixels since the skew and aspect ratio are decoupled from the other intrinsic parameters in /spl omega/.

Our work goes towards answering the growing need for the robust and efficient manipulation of curved objects in numerous applications. The kernel of the CGAL library provides several functionalities which are, however, mostly restricted to linear objects. We focus here on the arrangement of conic arcs in the plane. Our first contribution is the design, implementation and testing of a kernel for computing arrangements of circular arcs.A preliminary C++ implementation exists also for arbitrary conic curves. We discuss the representation and predicates of the geometric objects. Our implementation is targeted for inclusion in the CGAL library. Our second contribution concerns exact and efficient algebraic algorithms for the case of conics. They treat all inputs, including degeneracies, and they are implemented as part of the library SYNAPS 2.1.Our tools include Sturm sequences, resultants, Descartes' rule, andisolating points. Thirdly, our experiments on circular arcs show that our methods compare favorably to existing alternatives using CORE 1.6x and LEDA 4.5.

Given a triangulation in the plane or a tetrahedralization in 3-space, we investigate the efficiency of locating a point by walking in the structure with different strategies.

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

The purpose of this paper is to present a new method to design exact geometric predicates in algorithms dealing with curved objects such as circular arcs.We focus on the comparison of the abscissae of two intersection points of circle arcs, which is known to be a difficult predicate involved in the computation of arrangements of circle arcs.We present an algorithm for deciding the x-order of intersections from the signs of the coefficients of a polynomial, obtained by a general approach based on resultants.This method allows the use of efficient arithmetic and filtering techniques leading to fast implementation as shown by the experimental results. I. INTRODUCTIONImplementing geometric algorithms is difficult because the decisions made by such algorithms are taken on the basis of simple geometric questions, called predicates, solved by the evaluation of continuous functions subject to rounding errors, though the algorithms are basically of combinatorial and discrete nature.For example, the sweep line paradigm is a combinatorial algorithm relying on predicates such as x-comparisons.The use of floating point arithmetic to evaluate predicates often produces inconsistencies.For instance, plane sweep algorithms, which are basic tools in computational geometry, are known to be very sensitive to numerical errors: when computing arrangements of curves, a plane sweep algorithm needs to sort intersection points between curves by x coordinates, and if, due to erroneous numerical computations, the x comparison test is not transitive, the algorithm may crash.To cope with this problem, people may either work on the *This research

No abstract available.

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.

We study two problems related to planar motion planning for robots with imperfect control, where, if the robot starts a linear movement in a certain commanded direction, we only know that its actual movement will be confined in a cone of angle α centered around the specified direction. First, we consider a single goal region, namely the “region at infinity”, and a set of polygonal obstacles, modeled as a set S of n line segments. We are interested in the region Rα(S) from where we can reach infinity with a directional uncertainty of α. We prove that the maximum complexity of Rα(S) is O(nα5). Second, we consider a collection of k polygonal goal regions of total complexity m, but without any obstacles. Here we prove an O(k3m) bound on the complexity of the region from where we can reach a goal region with a directional uncertainty of α. For both situations we also prove lower bounds on the maximum complexity, and we give efficient algorithms for computing the regions.

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.