Intersection of Paraboloids and Application to Minkowski-Type Problems
Reflector generated by our algorithm (in less than 10 minutes).
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^2) 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 SoCG’14 (Annual ACM Symposium on Computational Geometry), 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.
Invariances of Single Curved Manifolds Applied to Mesh Segmentation
Detecting developable regions.
Recently, 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.
Simple and Efficient Distribution-Sensitive Point Location, in Triangulations
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.
On the asymptotic growth rate of some spanning trees embedded in R^d
We show that, for an Euclidean minimal k-insertion tree (EMIT_k) with n vertices, if the weight w of an edge e is its Euclidean length to the power of α, the sum of all w(e), with e ∈ EMIT_k, is O(n · k^−α/d) in the worst case, where d is the dimension, for d ≥ 2 and 0 < α < d. We also analyze the expected size of EMIT_k and some stars, when the points are evenly distributed inside the unit ball, for any α > 0.
The paper has been published in Operation Research Letters, and can be found here.
Robust and Efficient Delaunay Triangulations of Points on or Close to a Sphere
Delaunay triangulation of 20950 weather stations all around the world
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 (new 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.
Fast Delaunay Triangulation for Converging Point Relocation Sequences
Obtaining some tolerance regions
Updating a Delaunay triangulation when its vertices move is a bottleneck in several domains of application. Rebuilding the whole triangulation from scratch is surprisingly a very viable option compared to relocating the vertices. This can be explained by several recent advances in efficient construction of Delaunay triangulations. However, when all points move with a small magnitude, or when only a fraction of the vertices move, rebuilding is no longer the best option. This paper considers the problem of efficiently updating a Delaunay triangulation when its vertices are moving under small perturbations. The main contribution is a set of filters based upon the concept of vertex tolerances. Experiments show that filtering relocations is faster than rebuilding the whole triangulation from scratch under certain conditions.
The paper has been presented at SGP’09, and published in Computer Graphics Forum (Special issue 6th Annu. Sympos. Geometry Processing), and can be found here.
Design of the CGAL 3D Spherical Kernel and Application to Arrangements of Circles on a Sphere
Circles on Spheres with Exact Arithmetic
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.
Exact and efficient computations on circles in CGAL
Exact arithmetic for segment of 2D lines and circles.
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, and can be found here.