Publications

We show that converting Apollonius and Laguerre diagrams from an already built Delaunay triangulation of a set of n points in 2D requires at least Ώ(n log n) computation time. We also show that converting an Apollonius diagram of a set of n weighted points in 2D from a Laguerre diagram and vice-versa requires at least Ώ(n log n) computation time as well. Furthermore, we present a very simple randomized incremental construction algorithm that takes expected O(n log n) computation time to build an Apollonius diagram of non-overlapping circles in 2D.

The paper was presented at Canadian Conference on Computational Geometry 19 (CCCG’19), and published in the Proceedings of the 31st Canadian Conference on Computational Geometry, here is the link.

Let X be a d dimensional Poisson point process. We prove that the expected length of the Voronoi path between two points at distance 1 in the Delaunay triangulation associated with X is (2d/π)^1/2 + O(1/d^1/2) when d→∞. In any dimension, we also provide a precise interval containing the actual value; in 3D the expected length is between 1.4977 and 1.50007.

The paper is published in at Discrete and Computational Geometry and you can find here.

Given a planar subdivision with n vertices, each face having a cone of possible directions of travel, our goal is to decide which vertices of the subdivision can be reached from a given starting point s. We give an O(n log n)-time algorithm for this problem, as well as an Ώ(n log n) lower bound in the algebraic computation tree model. We prove that the generalization where two cones of directions per face are allowed is NP-hard.

The paper was presented at the Annual ACM Symposium on Computational Geometry 2017 (SoCG’17), and published in the Proceedings of SoCG 2017, here is the link. The journal version of the paper is yet an ongoing work.

We study the intersection (or union) of the convex hull of n confocal paraboloids (or ellipsoids) of revolution. This study is motivated by a Minkowski-type problem arising in geometric optics. We show that in each of the four cases, the combinatorics is given by the intersection of a power diagram with the unit sphere. We prove the complexity is O(n) for the intersection of paraboloids and O(n²) for the intersection and the union of ellipsoids. We provide an algorithm to compute these intersections using the exact geometric computation paradigm. This algorithm is optimal in the case of the intersection of ellipsoids and is used to numerically solve the far-field reflector problem.

The paper was presented at the Annual ACM Symposium on Computational Geometry 2014 (SoCG’14), and published in the Proceedings of SoCG 2014, here is the link. There is also a journal version of this work at Numerische & Mathematik, and can be found here.

It has been shown that, for Lambert illumination model, solely scenes composed by developable objects with a very particular albedo distribution produce an (2D) image with isolines that are (almost) invariant to light direction change. In this work, we provide and investigate a more general framework; and we show that, in general, the requirement for such invariances is quite strong, and is related to the differential geometry of the objects. More precisely, it is proved that single curved manifolds, i.e., manifolds such that at each point there is at most one principal curvature direction, produce invariant isosurfaces for a certain relevant family of energy functions. In the three-dimensional case, the associated energy function corresponds to the classical Lambert illumination model with albedo. This result is also extended for finite-dimensional scenes composed by single curved objects.

The paper has been presented at SIBGRAPI’12 (Conference on Graphics, Patterns and Images), and published in the Proceedings of SIBGRAPI 2012 (XXV Conference on Graphics, Patterns and Images), pages 158-165, 2012, and can be found here. There is a journal version of this work at Computer & Graphics, and can be found here.

We analyze, implement, and evaluate a distribution-sensitive point location algorithm based on the classical Jump & Walk, called Keep, Jump, & Walk. For a batch of query points, the main idea is to use previous queries to improve the current one. In practice, Keep, Jump, & Walk is actually a very competitive method to locate points in a triangulation. Regarding point location in a Delaunay triangulation, we show how the Delaunay hierarchy can be used to answer, under some hypotheses, a query q with a O(log#(pq)) randomized expected complexity, where p is a previously located query and #(s) indicates the number of simplices crossed by the line segment s. The Delaunay hierarchy has O(n log n) time complexity and O(n) memory complexity in the plane, and under certain realistic hypothe- ses these complexities generalize to any finite dimension. Finally, we combine the good distribution-sensitive behavior of Keep, Jump, & Walk, and the good complexity of the Delaunay hierarchy, into a novel point location algorithm called Keep, Jump, & Climb. To the best of our knowledge, Keep, Jump, & Climb is the first practical distribution-sensitive algorithm that works both in theory and in practice for Delaunay triangulations.

The paper has been presented at ALENEX’11, and published in the Workshop on Algorithm Engineering and Experiments, pages 127-138, 2011, and can be found here. We also have produced a JavaScript program demonstrating some of these strategies, see here; this program has been presented as a demo at SoCG’11, and can be found in Proceedings of 27th Annual Symposium on Computational Geometry, pages 295-296, 2011. There is a journal version of this paper been published at CAGD that you can find here.

We propose two ways to compute the Delaunay triangulation of points on a sphere, or of rounded points close to a sphere, both based on the classic incremental algorithm initially designed for the plane. We use the so-called space of circles as mathematical background for this work. We present a fully robust implementation built upon existing generic algorithms provided by the CGAL library. The efficiency of the implementation is established by benchmarks.

The paper has been presented at SEA’10 (old WEA), and published in the Proceedings of the 9th International Symposium on Experimental Algorithms, volume 6049 of Lecture Notes in Computer Science, pages 462-473, 2010 , and can be found here.

This paper presents a CGAL kernel for algorithms manipulating 3D spheres, circles, and circular arcs. The paper makes three contributions. First, the mathematics underlying two non-trivial predicates are presented. Second, the design of the kernel concept is developed, and the connexion between the mathematics and this design is established. In particular, we show how two different frameworks can be combined: one for the general setting, and one dedicated to the case where all the objects handled lie on a reference sphere. Finally, an assessment about the efficacy of the 3D Spherical Kernel is made through the calculation of the exact arrangement of circles on a sphere. On average while computing arrangements with few degeneracies (on sample molecular models), it is shown that certifying the result incurs a modest factor of two with respect to calculations using a plain double arithmetic.

This work has been implemented in CGAL, you can find the user manual here, and the reference manual here . The paper has been published in Computational Geometry: Theory and Applications , and can be found here.

CGAL (Computational Geometry Algorithms Library) is a large collection of geometric objects, data structures and algorithms. CGAL currently offers mostly functionalities for linear objects (points, segments, lines, triangles…). The first version of a kernel for circles and circular arcs in 2D was recently released in CGAL 3.2. We show in this paper a variety of techniques that we tested to improve the efficiency of the 2D circular kernel. These improvements are motivated by applications to VLSI design, and real VLSI industrial data are used to measure the impact of the techniques used to enhance this kernel. The improvements will be integrated in CGAL 3.3.

This work has been implemented in CGAL, you can find the user manual here, and the reference manual here . The paper has been presented at EWCG’07, and published in Abstracts of the 23rd European Workshop on Computational Geometry, pages 219-222, 2007.