TEILLAUD , Monique

Though Delaunay triangulations are very well known geometric data structures, the problem of the robust removal of a vertex in a three-dimensional Delaunay triangulation is still a problem in practice. We propose a simple method that allows to remove any vertex even when the points are in very degenerate configurations. The solution is...

In this paper, we study a sweeping algorithm for computing the arrangement of a set of quadrics in $\RR^{3}$. We define a ``trapezoidal'' decomposition in the sweeping plane, and we study the evolution of this subdivision during the sweep. A key point of this algorithm is the manipulation of algebraic numbers. In this perspective, we put a...

In this paper, we propose an algorithm to compute the Delaunay triangulation of a set of n points in 3-dimensional space when the points lie in 2 planes. The algorithm is output-sensitive and optimal with respect to the input and the output sizes. Its time complexity is O(n log n+t), where t is the size of the output, and the extra storage is O(n).

Curve offsets are important objects in computer-aided design. We study the algebraic properties of the offset to an algebraic curve, thus obtaining a general formula for its degree. This is applied to computing the degree of the offset to conics. We also compute an implicit equation of the generalised offset to a conic by using sparse...

Disponible dans les fichiers attachés à document

International audience

This article introduces the absolute quadratic complex formed by all lines that intersect the absolute conic. If ω denotes the 3 × 3 symmetric matrix representing the image of that conic under the action of a camera with projection matrix P, it is shown that ω ≈ P~Ω_P~T where V is the 3 × 6 line projection matrix associated with P and Ω_ is a 6...

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...

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...