Jean-daniel Boissonnat, Subir Kumar Ghosh, Sylvain Lazard
A linear time algorithm for computing a convex path of bounded curvature in a simple polygon
Incremental construction of the Delaunay graph in medium dimension (2009)
Boissonnat, Jean-Daniel, Devillers, Olivier, Hornus, Samuel
We describe a new implementation of the well-known incremental algorithm for constructing Delaunay triangulations in any dimension. Our implementation follows the exact computing paradigm and is...
Incremental construction of the Delaunay graph in medium dimension (2009)
Boissonnat, Jean-Daniel, Devillers, Olivier, Hornus, Samuel
We describe a new implementation of the well-known incremental algorithm for constructing Delaunay triangulations in any dimension. Our implementation follows the exact computing paradigm and is...
Feature preserving Delaunay mesh generation from 3D multi-material images (2009)
Boltcheva, Dobrina, Yvinec, Mariette, Boissonnat, Jean-Daniel
Generating realistic geometric models from 3D segmented images is an important task in many biomedical applications. Segmented 3D images impose particular challenges for meshing algorithms because...
Feature preserving Delaunay mesh generation from 3D multi-material images (2009)
Boltcheva, Dobrina, Yvinec, Mariette, Boissonnat, Jean-Daniel
Generating realistic geometric models from 3D segmented images is an important task in many biomedical applications. Segmented 3D images impose particular challenges for meshing algorithms because...
Mesh generation from 3D multi-material images (2009)
Boltcheva, Dobrina, Yvinec, Mariette, Boissonnat, Jean-Daniel
The problem of generating realistic computer models of objects represented by 3D segmented images is important in many biomedical applications. Labelled 3D images impose particular challenges for...
Mesh generation from 3D multi-material images (2009)
Boltcheva, Dobrina, Yvinec, Mariette, Boissonnat, Jean-Daniel
The problem of generating realistic computer models of objects represented by 3D segmented images is important in many biomedical applications. Labelled 3D images impose particular challenges for...
Stability and computation of medial axes – a state-of-the-art report (2008)
Dominique Attali, Jean-daniel Boissonnat, Herbert Edelsbrunner
Summary. The medial axis of a geometric shape captures its connectivity. In spite of its inherent instability, it has found applications in a number of areas that deal with shapes. In this survey...
Shape Reconstruction from Unorganized Cross-sections (2008)
Er Belyaev, Michael Garl, Jean-daniel Boissonnat, Pooran Memari
In this paper, we consider the problem of reconstructing a shape from unorganized cross-sections. The main motivation for this problem comes from medical imaging applications where cross-sections of...
Stability and computation of medial axes – a state-of-the-art report (2008)
Dominique Attali, Jean-daniel Boissonnat, Herbert Edelsbrunner
Summary. The medial axis of a geometric shape captures its connectivity. In spite of its inherent instability, it has found applications in a number of areas that deal with shapes. In this survey...
Jean-daniel Boissonnat, Menelaos I. Karavelas
In this paper we show an equivalence relationship between additively weighted Voronoi cells in Rd, power diagrams in Rd and convex hulls of spheres in Rd. An immediate consequence of this equivalence...
Jean-daniel Boissonnat, Menelaos I. Karavelas, Jean-daniel Boissonnat, Menelaos I. Karavelas, Thème Génie Logiciel, Projet Prisme
Voronoi cells and convex hulls of d-dimensional
Jean-daniel Boissonnat, Isotopic Implicit, Surface Meshing
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...
published in Algorithmica 30, 2001, p.67–82. Circular Separability of Polygons ∗ (2008)
Jean-daniel Boissonnat, Jurek Czyzowicz, Olivier Devillers, Mariette Yvinec
Two planar sets are circularly separable if there exists a circle enclosing one of the sets and whose open interior disk does not intersect the other set. This paper studies two problems related to...
Frank Nielsen, Jean-daniel Boissonnat, Richard Nock
Voronoi diagrams are fundamental geometric structures that partition the space into elementary regions of influence defining discrete proximity graphs and dually well-shaped Delaunay triangulations...
Abstract On Bregman Voronoi Diagrams ∗ (2008)
Frank Nielsen, Jean-daniel Boissonnat, Richard Nock
The Voronoi diagram of a point set is a fundamental geometric structure that partitions the space into elementary regions of influence defining a discrete proximity graph and dually a well-shaped...
ABSTRACT Provably Good Sampling and Meshing of Lipschitz Surfaces (2008)
In the last decade, a great deal of work has been devoted to the elaboration of a sampling theory for smooth surfaces. The goal was to ensure a good reconstruction of a given surface S from a finite...
Learning Smooth Shapes by Probing (2008)
Jean-daniel Boissonnat, Leonidas J. Guibas, Steve Oudot
We consider the problem of discovering a smooth unknown surface S bounding an object O in R 3. The discovery process consists of moving a point probing device in the free space around O so that it...
ABSTRACT Manifold Reconstruction in Arbitrary Dimensions using Witness Complexes (2008)
It is a well-established fact that the witness complex is closely related to the restricted Delaunay triangulation in low dimensions. Specifically, it has been proved that the witness complex...
Abstract Anisotropic Diagrams: Labelle Shewchuk approach revisited ∗ (2008)
Jean-daniel Boissonnat, Camille Wormser, Mariette Yvinec
F. Labelle and J. Shewchuk [3] have proposed a discrete definition of anisotropic Voronoi diagrams. These diagrams are parametrized by a metric field. Under mild hypotheses on the metric field, such...
Sujet de stage --- Annee 2004 - 2005 (2008)
Calcul Un Axe, Dominique Attali, Jean-daniel Boissonnat
e que le #-axe median est une partie stable de l'axe median [4] (voir Figure 2). Cependant, il n'est pas clair de savoir quelle valeur de # convient le mieux et parfois, il n'existe...
Locally Uniform Anisotropic Meshing (2008)
Boissonnat, Jean-Daniel, Wormser, Camille, Yvinec, Mariette
Anisotropic meshes are triangulations of a given domain in the plane or in higher dimensions, with elements elongated along prescribed directions. Anisotropic triangulations have been shown to be...
Locally Uniform Anisotropic Meshing (2008)
Boissonnat, Jean-Daniel, Wormser, Camille, Yvinec, Mariette
Anisotropic meshes are triangulations of a given domain in the plane or in higher dimensions, with elements elongated along prescribed directions. Anisotropic triangulations have been shown to be...
Anisotropic Diagrams: Labelle Shewchuk approach revisited (2008)
Boissonnat, Jean-Daniel, Wormser, Camille, Yvinec, Mariette
F. Labelle and J. Shewchuk have proposed a discrete definition of anisotropic Voronoi diagrams. These diagrams are parametrized by a metric field. Under mild hypotheses on the metric...
Anisotropic Diagrams: Labelle Shewchuk approach revisited (2008)
Boissonnat, Jean-Daniel, Wormser, Camille, Yvinec, Mariette
F. Labelle and J. Shewchuk have proposed a discrete definition of anisotropic Voronoi diagrams. These diagrams are parametrized by a metric field. Under mild hypotheses on the metric...
An efficient implementation of Delaunay triangulations in medium dimensions (2008)
Hornus, Samuel, Boissonnat, Jean-Daniel
We propose a new C++ implementation of the well-known incremental algorithm for the construction of Delaunay triangulations in any dimension. Our implementation follows the exact computing paradigm...
An efficient implementation of Delaunay triangulations in medium dimensions (2008)
Hornus, Samuel, Boissonnat, Jean-Daniel
We propose a new C++ implementation of the well-known incremental algorithm for the construction of Delaunay triangulations in any dimension. Our implementation follows the exact computing paradigm...
[summary by Brigitte Vall'ee, Universit'e de Caen] (2007)
Most decisions in geometric algorithms are based on signs of determinants. For example, deciding if a point belongs to a given half-space or a given ball reduces to evaluating the sign of a...
Robustesse Des Algorithmes Geometriques (2007)
Des Algorithmes, Jean-daniel Boissonnat, A. Lieutier, Matra Datavision
Introduction au calcul g#om#trique (a) Double nature des objets et des probl#mes g#om#triques (b) Pr#dicats et constructeurs, plongements (c) Notions de robustesse (d) Mod#les d'arithm#tique 2....
Slices of Minkowski differences and Satellite Antenna Layout (2007)
Jean-daniel Boissonnat, Eelco De Lange, Monique Teillaud
Satellite layout is a very hard task because available space for the instruments is small and the physical constraints on the layout are strong. In this article, we show how some physical layout...
de recherche Motion Planning of Legged Robots (2007)
Jean-daniel Boissonnat, Jean-daniel Boissonnat, Olivier Devillers, Olivier Devillers, Sylvain Lazard, Sylvain Lazard, ...
Abstract: We study the problem of computing the free space F of a simple legged robot called the spider robot. The body of this robot is a single point and the legs are attached to the body. The...
Circular Separability ofPolygons (2007)
Mariette Yvinec, Jean-daniel Boissonnat, Jean-daniel Boissonnat, Jurek Czyzowicz, Jurek Czyzowicz, Olivier Devillers, ...
novembre 94
1 CGAL: an overview CGAL, the Computational Geometry Algorithms Library (2007)
Jean-daniel Boissonnat, Frank Da, Olivier Devillers, Sylvain Pion, Monique Teillaud, Mariette Yvinec
is a large scaled project funded by the European Community. Its goal is to develop a body of objects and operations commonly used in computational geometry and to make them available to application...
Jean-daniel Boissonnat, Olivier Devillers, Monique Teillaud
The k-Delaunay tree extends the Delaunay tree introduced in [1, 2]. It is a hierarchical data structure that allows the semi-dynamic construction of the higher order Voronoi diagrams of a finite set...
Francis Avnaim, Jean-daniel Boissonnat, Olivier Devillers, Franco P. Preparata, Mariette Yvinec
signs of determinants using single-precision arithmetic
Jean-daniel Boissonnat, Olivier Devillers, Franco P. Preparata
We consider the problem of planning motions of a simple legged robot called the spider robot. The robot is modelled as a point where all its legs are attached, and the footholds where the robot can...
Louaï Adhami, Ève Coste-manière, Jean-daniel Boissonnat
This talk presents a framework for preparing and executing Minimal Invasive Surgery (MIS) using tele-operated robotic manipulators. The approach consists of a planning, validation, simulation,...
Jean-daniel Boissonnat, Olivier Devillers, Monique Teillaud
Communicated by D. T. Lee In this paper, we propose an algorithm to compute the Delaunay triangulation of a set S of n points in 3-dimensional space when the points lie in 2 planes. The algorithm is...
Jean-daniel Boissonnat, Sylvain Lazard
polynomial-time algorithm for computing a shortest path of
Jean-daniel Boissonnat, Jean-daniel Boissonnat, Sylvain Lazard, Sylvain Lazard
apport de recherche
Des Algorithmes, Jean-daniel Boissonnat, A. Lieutier, Matra Datavision
Mathematically, the problem of reporting intersecting segments is trivial. Computationally, the problem is far from easy, and be impossible to solve reliably and consistently. R. Forrest 1986 Dans...
Jean-daniel Boissonnat, Sylvain Lazard
A polynomial-time algorithm for computing a shortest path of
Jean-daniel Boissonnat, Jean-daniel Boissonnat, Olivier Devillers, Olivier Devillers, Sylvain Lazard, Sylvain Lazard
apport de recherche
Jean-daniel Boissonnat, Antoine Vigneron
Let E r and E b be two sets of non-intersecting curve segments, let E = E r [ E b. When jEj = n, we give a new sweep-line algorithm algorithm that reports the k intersecting pairs of segments of E....
Francis Avnaim, Francis Avnaim, Jean-daniel Boissonnat, Jean-daniel Boissonnat, Olivier Devillers, Olivier Devillers, ...
image et vision apport de recherche 1994 Evaluating signs of determinants using single-precision arithmetic
Computing the Diameter of a Point Set (2007)
Thmes Et, Grgoire Malandain, Jean-daniel Boissonnat, Jean-daniel Boissonnat
apport de recherche
Jean-daniel Boissonnat, Jean-daniel Boissonnat, Sylvain Lazard, Sylvain Lazard
apport de recherche
Motion Planning of Legged Robots: (2007)
Unite De Recherche, Inria-sophia Antipolis, Et En Automatique, Route Des Lucioles, Jean-daniel Boissonnat, ...
We consider the problem of planning motions of a simple legged robot called the spider robot. The robot is modelled as a point where all its legs are attached, and the footholds where the robot can...
Bregman Voronoi Diagrams: Properties, Algorithms and Applications (2007)
Nielsen, Frank, Boissonnat, Jean-Daniel, Nock, Richard
The Voronoi diagram of a finite set of objects is a fundamental geometric structure that subdivides the embedding space into regions, each region consisting of the points that are closer to a given...
Bregman Voronoi Diagrams: Properties, Algorithms and Applications (2007)
Boissonnat, Jean-Daniel, Nielsen, Frank, Nock, Richard
The Voronoi diagram of a finite set of objects is a fundamental geometric structure that subdivides the embedding space into regions, each region consisting of the points that are closer to a given...
Bregman Voronoi Diagrams: Properties, Algorithms and Applications (2007)
Boissonnat, Jean-Daniel, Nielsen, Frank, Nock, Richard
The Voronoi diagram of a finite set of objects is a fundamental geometric structure that subdivides the embedding space into regions, each region consisting of the points that are closer to a given...
Bregman Voronoi Diagrams: Properties, Algorithms and Applications (2007)
Boissonnat, Jean-Daniel, Nielsen, Frank, Nock, Richard
The Voronoi diagram of a finite set of objects is a fundamental geometric structure that subdivides the embedding space into regions, each region consisting of the points that are closer to a given...
Bregman Voronoi Diagrams: Properties, Algorithms and Applications (2007)
Boissonnat, Jean-Daniel, Nielsen, Frank, Nock, Richard
The Voronoi diagram of a finite set of objects is a fundamental geometric structure that subdivides the embedding space into regions, each region consisting of the points that are closer to a given...
Effective Computational Geometry for Curves and Surfaces (2007)
Jean-daniel Boissonnat, David Cohen-steiner, Bernard Mourrain, Günter Rote, Gert Vegter
Meshing is the process of computing, for a given surface, a representation consisting of pieces of simple surface patches, like triangles. This survey discusses all currently known surface (and...
Manifold reconstruction in arbitrary dimensions using witness complexes (2007)
Jean-daniel Boissonnat, Leonidas J. Guibas, Steve Y. Oudot
It is a well-established fact that the witness complex is closely related to the restricted Delaunay triangulation in low dimensions. Specifically, it has been proved that the witness complex...
Effective Computational Geometry for Curves and Surfaces (2007)
Jean-daniel Boissonnat, David Cohen-steiner, Bernard Mourrain, Günter Rote, Gert Vegter
Meshing is the process of computing, for a given surface, a representation consisting of pieces of simple surface patches, like triangles. This survey discusses all currently known surface (and...
A disk-covering problem with application in optical interferometry (2006)
Nguyen, Trung, Boissonnat, Jean-Daniel, Falzon, Frederic, Knauer, Christian
Given a disk O in the plane called the objective, we want to find n small disks P_1,...,P_n called the pupils such that $\bigcup_{i,j=1}^n P_i \ominus P_j \supseteq O$, where $\ominus$ denotes the...
Anisotropic Diagrams: Labelle Shewchuk approach revisited (2006)
Boissonnat, Jean-Daniel, Wormser, Camille, Yvinec, Mariette
F. Labelle and J. Shewchuk have proposed a discrete definition of anisotropic Voronoi diagrams. These diagrams are parametrized by a metric field. Under mild hypotheses on the metric field, such...
Anisotropic Diagrams: Labelle Shewchuk approach revisited (2006)
Boissonnat, Jean-Daniel, Wormser, Camille, Yvinec, Mariette
F. Labelle and J. Shewchuk have proposed a discrete definition of anisotropic Voronoi diagrams. These diagrams are parametrized by a metric field. Under mild hypotheses on the metric field, such...
Based on the Restricted Delaunay (2006)
Delaunay Deformable Models, Topology-adaptive Meshes, Jean-daniel Boissonnat, Topology-adaptive Meshes
Modèles déformables de Delaunay: maillages avec changements de topologie basés sur la triangulation de Delaunay restreinte
= {x ∈ Rd | ||pix| | ≤ ||pjx| | ∀pj ∈ S} (2006)
Frank Nielsen, Jean-daniel Boissonnat, Richard Nock, F. Nielsen, R. Nock, ...
p1 p5 p2 p6 Vor(p6) p7 p4 p3 Voronoi diagram Vor(S) s.t. Vor(pi) def
Alla Sheffer, Konrad Polthier, Barbara Cutler, Jean-daniel Boissonnat
These proceedings are available only in electronic version
the Euclidean distance ||x||2 = (2006)
Frank Nielsen, Jean-daniel Boissonnat, Richard Nock, F. Nielsen, R. Nock, ...
p1 p5 p2 p6 Vor(p6) p7 p4 p3 • Voronoi diagram Vor(S) s.t. Vor(pi) def = {x ∈ Rd | ||pix| | ≤ ||pjx| | ∀pj ∈ S} • Voronoi sites (static view). • Voronoi generators (dynamic view). →...
Anisotropic Diagrams: Labelle Shewchuk approach revisited (2005)
Boissonnat, Jean-Daniel, Wormser, Camille, Yvinec, Mariette
F. Labelle and J. Shewchuk have proposed a discrete definition of anisotropic Voronoi diagrams. These diagrams are parametrized by a metric field. Under mild hypotheses on the metric field, such...
Reconstruire des surfaces pour l'imagerie (2005)
Reconstituer une surface en ne connaissant que certains de ses points : un problème que l'on rencontre souvent, qu'il s'agisse d'exploration géologique, d'archivage de vestiges archéologiques,...
Reconstruire des surfaces pour l'imagerie (2005)
Reconstituer une surface en ne connaissant que certains de ses points : un problème que l'on rencontre souvent, qu'il s'agisse d'exploration géologique, d'archivage de vestiges archéologiques,...
Manipulation informatique des objets géométriques (2005)
Dans la vie courante, on a le plus souvent affaire à des objets tridimensionnels. On s'intéresse à leur forme, à leur orientation, etc. Pour les traiter informatiquement, on développe des...
Manipulation informatique des objets géométriques (2005)
Dans la vie courante, on a le plus souvent affaire à des objets tridimensionnels. On s'intéresse à leur forme, à leur orientation, etc. Pour les traiter informatiquement, on développe des...
Learning smooth objects by probing (2005)
We consider the problem of discovering a smooth unknown surface S bounding an object O in R 3. The discovery process consists of moving a point probing device in the free space around O so that it...
Learning Surfaces by Probing (2004)
Boissonnat, Jean-Daniel, Guibas, Leonidas J., Oudot, Steve
We consider the problem of discovering a smooth unknown surface S bounding an object O in R^3. The discovery process consists of moving a point probing device in the free space around O so that it...
Learning Surfaces by Probing (2004)
Boissonnat, Jean-Daniel, Guibas, Leonidas J., Oudot, Steve
We consider the problem of discovering a smooth unknown surface S bounding an object O in R^3. The discovery process consists of moving a point probing device in the free space around O so that it...
Learning Surfaces by Probing (2004)
Boissonnat, Jean-Daniel, Guibas, Leonidas J., Oudot, Steve
We consider the problem of discovering a smooth unknown surface S bounding an object O in R^3. The discovery process consists of moving a point probing device in the free space around O so that it...
Isotopic implicit surface meshing (2004)
Jean-daniel Boissonnat, David Cohen-steiner, Gert Vegter
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...
An Effective Condition for Sampling Surfaces with Guarantees (2003)
Boissonnat, Jean-Daniel, Oudot, Steve
The notion of -sample, as introduced by Amenta and Bern, has proven to be a key concept in the theory of sampled surfaces. Of particular interest is the fact that, if E is an -sample of a smooth...
Meshing implicit surfaces with certified topology title (2003)
Boissonnat, Jean-Daniel, Cohen-Steiner, David, Vegter, Gert
We describe a new algorithm for building piecewise linear approximations of an implicit surface. This algorithm is the first one guaranteeing that the implicit surface and its approximation are...
An Effective Condition for Sampling Surfaces with Guarantees (2003)
Boissonnat, Jean-Daniel, Oudot, Steve
The notion of -sample, as introduced by Amenta and Bern, has proven to be a key concept in the theory of sampled surfaces. Of particular interest is the fact that, if E is an -sample of a smooth...
Meshing implicit surfaces with certified topology title (2003)
Boissonnat, Jean-Daniel, Cohen-Steiner, David, Vegter, Gert
We describe a new algorithm for building piecewise linear approximations of an implicit surface. This algorithm is the first one guaranteeing that the implicit surface and its approximation are...
An Effective Condition for Sampling Surfaces with Guarantees (2003)
Boissonnat, Jean-Daniel, Oudot, Steve
The notion of -sample, as introduced by Amenta and Bern, has proven to be a key concept in the theory of sampled surfaces. Of particular interest is the fact that, if E is an -sample of a smooth...
Meshing implicit surfaces with certified topology title (2003)
Boissonnat, Jean-Daniel, Cohen-Steiner, David, Vegter, Gert
We describe a new algorithm for building piecewise linear approximations of an implicit surface. This algorithm is the first one guaranteeing that the implicit surface and its approximation are...
Provably Good Surface Sampling and Approximation (2003)
Steve Oudot, Jean-daniel Boissonnat
We present an algorithm for meshing surfaces that is a simple adaptation of a greedy "farthest point" technique proposed by Chew. Given a surface S, it progressively adds points on S and...
Meshing Implicit Surfaces with Certified Topology (2003)
Jean-daniel Boissonnat, David Cohen-Steiner, Gert Vegter
We address the problem of isosurface meshing with topological guaranties. Assuming the critical points of the considered function are given, we give a certified algorithm for this problem. This seems...
A coordinate system on a surface: definition, properties and applications (2002)
Boissonnat, Jean-Daniel, Flötotto, Julia
Coordinate systems associated to a finite set of sample points have been extensively studied, especially in the context of interpolation of multivariate scattered data. Notably, Sibson proposed the...
Boissonnat, Jean-Daniel, Karavelas, Menelaos I.
In this paper we show an equivalence relationship between additively weighted Voronoi cells in R [power d], power diagrams in R [power d] and convex hulls of spheres in R [power d]. An immediate...
Attali, Dominique, Boissonnat, Jean-Daniel
Delaunay triangulations and Voronoi diagrams have found numerous applications in surface modeling, surface mesh generation, deformable surface modeling and surface reconstruction. Many algorithms in...
Conforming Orthogonal Meshes (2002)
Balaven, Sophie, Bennis, Chakib, Boissonnat, Jean-Daniel, Yvinec, Mariette
In this paper, we show how to compute an orthogonal mesh that strictly conforms to a given simplicial complex SC in ^d. This result will be applied to improve the treatment of wells in oil reservoir...
A coordinate system on a surface: definition, properties and applications (2002)
Boissonnat, Jean-Daniel, Flötotto, Julia
Coordinate systems associated to a finite set of sample points have been extensively studied, especially in the context of interpolation of multivariate scattered data. Notably, Sibson proposed the...
Boissonnat, Jean-Daniel, Karavelas, Menelaos I.
In this paper we show an equivalence relationship between additively weighted Voronoi cells in R [power d], power diagrams in R [power d] and convex hulls of spheres in R [power d]. An immediate...
Attali, Dominique, Boissonnat, Jean-Daniel
Delaunay triangulations and Voronoi diagrams have found numerous applications in surface modeling, surface mesh generation, deformable surface modeling and surface reconstruction. Many algorithms in...
Conforming Orthogonal Meshes (2002)
Balaven, Sophie, Bennis, Chakib, Boissonnat, Jean-Daniel, Yvinec, Mariette
In this paper, we show how to compute an orthogonal mesh that strictly conforms to a given simplicial complex SC in ^d. This result will be applied to improve the treatment of wells in oil reservoir...
A coordinate system on a surface: definition, properties and applications (2002)
Boissonnat, Jean-Daniel, Flötotto, Julia
Coordinate systems associated to a finite set of sample points have been extensively studied, especially in the context of interpolation of multivariate scattered data. Notably, Sibson proposed the...
Boissonnat, Jean-Daniel, Karavelas, Menelaos I.
In this paper we show an equivalence relationship between additively weighted Voronoi cells in R [power d], power diagrams in R [power d] and convex hulls of spheres in R [power d]. An immediate...
Attali, Dominique, Boissonnat, Jean-Daniel
Delaunay triangulations and Voronoi diagrams have found numerous applications in surface modeling, surface mesh generation, deformable surface modeling and surface reconstruction. Many algorithms in...
Conforming Orthogonal Meshes (2002)
Balaven, Sophie, Bennis, Chakib, Boissonnat, Jean-Daniel, Yvinec, Mariette
In this paper, we show how to compute an orthogonal mesh that strictly conforms to a given simplicial complex SC in ^d. This result will be applied to improve the treatment of wells in oil reservoir...
Boissonnat, Jean-Daniel, Devillers, Olivier, Pion, Sylvain, Teillaud, Monique, Yvinec, Mariette
This paper presents the main algorithmic and design choices that have been made to implement triangulations in the computational geometry algorithms library CGAL.
Boissonnat, Jean-Daniel, Devillers, Olivier, Pion, Sylvain, Teillaud, Monique, Yvinec, Mariette
This paper presents the main algorithmic and design choices that have been made to implement triangulations in the computational geometry algorithms library CGAL.
Computing the diameter of a point set (2002)
Abstract. Given a nite set of points P in R d, the diameter of P is de ned as the maximum distance between two points of P. We propose a very simple algorithm to compute the diameter of a nite set of...
Complexity of the Delaunay triangulation of points on polyhedral surfaces (2001)
Attali, Dominique, Boissonnat, Jean-Daniel
It is well known that the complexity of the Delaunay triangulation of $n$ points in $R ^d$, i.e. the number of its simplices, can be $\Omega (n^\lceil \frac{d{2}\rceil })$. In particular, in $R ^3$,...
Computing the Diameter of a Point Set (2001)
Malandain, Grégoire, Boissonnat, Jean-Daniel
Given a finite set of points $\cal P$ in $\mathbb{R}^d$, the diameter of $\cal P$ is defined as the maximum distance between two points of $\cal P$. We propose a very simple algorithm to compute the...
Complexity of the Delaunay triangulation of points on polyhedral surfaces (2001)
Attali, Dominique, Boissonnat, Jean-Daniel
It is well known that the complexity of the Delaunay triangulation of $n$ points in $R ^d$, i.e. the number of its simplices, can be $\Omega (n^\lceil \frac{d{2}\rceil })$. In particular, in $R ^3$,...
Computing the Diameter of a Point Set (2001)
Malandain, Grégoire, Boissonnat, Jean-Daniel
Given a finite set of points $\cal P$ in $\mathbb{R}^d$, the diameter of $\cal P$ is defined as the maximum distance between two points of $\cal P$. We propose a very simple algorithm to compute the...
Circular Separability of Polygons (2001)
Boissonnat, Jean-Daniel, Czyzowicz, Jurek, Devillers, Olivier, Yvinec, Mariette
Two planar sets are circularly separable if there exists a circle enclosing one of the set and whose open interior disk does not intersect the other set. This paper studies two problems related to...
Circular Separability of Polygons (2001)
Boissonnat, Jean-Daniel, Czyzowicz, Jurek, Devillers, Olivier, Yvinec, Mariette
Two planar sets are circularly separable if there exists a circle enclosing one of the set and whose open interior disk does not intersect the other set. This paper studies two problems related to...
Complexity of the Delaunay triangulation of points on polyhedral surfaces (2001)
Attali, Dominique, Boissonnat, Jean-Daniel
It is well known that the complexity of the Delaunay triangulation of $n$ points in $R ^d$, i.e. the number of its simplices, can be $\Omega (n^\lceil \frac{d{2}\rceil })$. In particular, in $R ^3$,...
Computing the Diameter of a Point Set (2001)
Malandain, Grégoire, Boissonnat, Jean-Daniel
Given a finite set of points $\cal P$ in $\mathbb{R}^d$, the diameter of $\cal P$ is defined as the maximum distance between two points of $\cal P$. We propose a very simple algorithm to compute the...
Circular Separability of Polygons (2001)
Boissonnat, Jean-Daniel, Czyzowicz, Jurek, Devillers, Olivier, Yvinec, Mariette
Two planar sets are circularly separable if there exists a circle enclosing one of the set and whose open interior disk does not intersect the other set. This paper studies two problems related to...
Natural Neighbour Coordinates of Points on a Surface (2001)
Natural neighbour coordinates and natural neighbour interpolation have been introduced by Sibson for interpolating multivariate scattered data. In this paper, we consider the case where the data...
Computing the Diameter of a Point Set (2001)
Grégoire Malandain, Grégoire Mal, Jean-daniel Boissonnat, Unité Inria, ...
Given a #nite set of points in R is de#ned as the maximum distance between two points of . We propose a very simple algorithm to compute the diameter of a #nite set of points. Although the algorithm...
An Elementary Algorithm for Reporting Intersections of Red/Blue Curve Segments (2000)
Boissonnat, Jean-Daniel, Vigneron, Antoine
Let E_r and E_b be two sets of x-monotone and non-intersecting curve segments, E=E_r \cup E_b and |E|=n. We give a new sweep-line algorithm that reports the $k$ intersecting pairs of segments of E....
Natural Neighbour Coordinates of Points on a Surface (2000)
Boissonnat, Jean-Daniel, Cazals, Frédéric
Natural neighbour coordinates and natural neighbour interpolation have been introduced by Sibson for interpolating multivariate scattered data. In this paper, we consider the case where the data...
Smooth Surface Reconstruction via Natural Neighbour Interpolation of Distance Functions (2000)
Boissonnat, Jean-Daniel, Cazals, Frédéric
We present an algorithm to reconstruct smooth surfaces of arbitrary topology from unorganised sample points and normals. The method uses natural neighbour interpolation, works in any dimension and...
An Elementary Algorithm for Reporting Intersections of Red/Blue Curve Segments (2000)
Boissonnat, Jean-Daniel, Vigneron, Antoine
Let E_r and E_b be two sets of x-monotone and non-intersecting curve segments, E=E_r \cup E_b and |E|=n. We give a new sweep-line algorithm that reports the $k$ intersecting pairs of segments of E....
Natural Neighbour Coordinates of Points on a Surface (2000)
Boissonnat, Jean-Daniel, Cazals, Frédéric
Natural neighbour coordinates and natural neighbour interpolation have been introduced by Sibson for interpolating multivariate scattered data. In this paper, we consider the case where the data...
Smooth Surface Reconstruction via Natural Neighbour Interpolation of Distance Functions (2000)
Boissonnat, Jean-Daniel, Cazals, Frédéric
We present an algorithm to reconstruct smooth surfaces of arbitrary topology from unorganised sample points and normals. The method uses natural neighbour interpolation, works in any dimension and...
An Elementary Algorithm for Reporting Intersections of Red/Blue Curve Segments (2000)
Boissonnat, Jean-Daniel, Vigneron, Antoine
Let E_r and E_b be two sets of x-monotone and non-intersecting curve segments, E=E_r \cup E_b and |E|=n. We give a new sweep-line algorithm that reports the $k$ intersecting pairs of segments of E....
Natural Neighbour Coordinates of Points on a Surface (2000)
Boissonnat, Jean-Daniel, Cazals, Frédéric
Natural neighbour coordinates and natural neighbour interpolation have been introduced by Sibson for interpolating multivariate scattered data. In this paper, we consider the case where the data...
Smooth Surface Reconstruction via Natural Neighbour Interpolation of Distance Functions (2000)
Boissonnat, Jean-Daniel, Cazals, Frédéric
We present an algorithm to reconstruct smooth surfaces of arbitrary topology from unorganised sample points and normals. The method uses natural neighbour interpolation, works in any dimension and...
Computing Largest Circles Separating Two Sets of Segments (2000)
Boissonnat, Jean-Daniel, Czyzowicz, Jurek, Devillers, Olivier, Urrutia, Jorge, Yvinec, Mariette
A circle C separates two planar sets if it encloses one of the sets and its open interior disk does not meet the other set. A separating circle is a largest one if it cannot be locally increased...
Motion Planning of Legged Robots (2000)
Boissonnat, Jean-Daniel, Devillers, Olivier, Lazard, Sylvain
We study the problem of computing the free space F of a simple legged robot called the spider robot. The body of this robot is a single point and the legs are attached to the body. The robot is...
Computing Largest Circles Separating Two Sets of Segments (2000)
Boissonnat, Jean-Daniel, Czyzowicz, Jurek, Devillers, Olivier, Urrutia, Jorge, Yvinec, Mariette
A circle C separates two planar sets if it encloses one of the sets and its open interior disk does not meet the other set. A separating circle is a largest one if it cannot be locally increased...
Motion Planning of Legged Robots (2000)
Boissonnat, Jean-Daniel, Devillers, Olivier, Lazard, Sylvain
We study the problem of computing the free space F of a simple legged robot called the spider robot. The body of this robot is a single point and the legs are attached to the body. The robot is...
Smooth Surface Reconstruction via Natural Neighbour Interpolation of Distance Functions (2000)
Jean-daniel Boissonnat, Frdric Cazals
We present an algorithm to reconstruct smooth surfaces of arbitrary topology from unorganised sample points and normals. The method uses natural neighbour interpolation, works in any dimension and...
Motion planning of legged robots (2000)
Jean-daniel Boissonnat, Olivier Devillers, Sylvain Lazard
Abstract. We study the problem of computing the free space F of a simple legged robot called the spider robot. The body of this robot is a single point and the legs are attached to the body. The...
Planning and simulation of robotically assisted minimal invasive surgery (2000)
Louaï Adhami, Ève Coste-manière, Jean-daniel Boissonnat
Abstract. This paper proposes a framework for pre-operative planning and simulation of robotically assisted Minimal Invasive Surgery (MIS). The design of an integrated system is presented for...
Ève Coste-manière, Louaï Adhami, Renaud Severac-bastide, Adrian Lobontiu, J. Kenneth, Jean-daniel Boissonnat, ...
Abstract. This work presents the first experimental results of an ongoing cooperation between medical, robotics and computer science teams aimed at optimizing the use of robotic systems in minimally...
Elementary Algorithms for Reporting Intersections of Curve Segments (1999)
Boissonnat, Jean-Daniel, Vigneron, Antoine
We propose several algorithms to report the k intersecting pairs among a set of n curve segments. Apart from the intersection predicate, our algorithms only use two simple predicates : the predicate...
Convex Tours of Bounded Curvature (1999)
Boissonnat, Jean-Daniel, Czyzowicz, Jurek, Devillers, Olivier, Robert, Jean-Marc, Yvinec, Mariette
We consider the motion planning problem for a point constrained to move along a smooth closed convex path of bounded curvature. The workspace of the moving point is bounded by a convex polygon with m...
Computing largest circles separating two sets of segments (1999)
Boissonnat, Jean-Daniel, Czyzowicz, Jurek, Devillers, Olivier, Urrutia, Jorge, Yvinec, Mariette
A circle $C$ separates two planar sets if it encloses one of the sets and its open interior disk does not meet the other set. A separating circle is a largest one if it cannot be locally increased...
Motion Planning of Legged Robots (1999)
Boissonnat, Jean-Daniel, Devillers, Olivier, Lazard, Sylvain
We study the problem of computing the free space F of a simple legged robot called the spider robot. The body of this robot is a single point and the legs are attached to the body. The robot is...
Circular Separability of Polygons (1999)
Boissonnat, Jean-Daniel, Czyzowicz, Jurek, Devillers, Olivier, Yvinec, Mariette
Two planar sets are circularly separable if there exists a circle enclosing one of the sets and whose open interior disk does not intersect the other set. This paper studies two problems related to...
Elementary Algorithms for Reporting Intersections of Curve Segments (1999)
Boissonnat, Jean-Daniel, Vigneron, Antoine
We propose several algorithms to report the k intersecting pairs among a set of n curve segments. Apart from the intersection predicate, our algorithms only use two simple predicates : the predicate...
Elementary Algorithms for Reporting Intersections of Curve Segments (1999)
Boissonnat, Jean-Daniel, Vigneron, Antoine
We propose several algorithms to report the k intersecting pairs among a set of n curve segments. Apart from the intersection predicate, our algorithms only use two simple predicates : the predicate...
Programming with CGAL: the example of triangulations (1999)
Boissonnat, Jean-Daniel, Cazals, Frédéric, Da, Tran Kai Frank, Devillers, Olivier, Pion, Sylvain, Rebufat, Francois, ...
This paper accompanies a video presenting how to develop code using CGAL, in particular, the triangulation classes.
Programming with CGAL: the example of triangulations (1999)
Boissonnat, Jean-Daniel, Cazals, Frédéric, Da, Tran Kai Frank, Devillers, Olivier, Pion, Sylvain, Rebufat, Francois, ...
This paper accompanies a video presenting how to develop code using CGAL, in particular, the triangulation classes.
Elementary algorithms for reporting intersections of curve segments (1999)
Jean-daniel Boissonnat, Antoine Vigneron
Let E r and E b be two sets of x-monotone and non-intersecting curve segments, E = E r [ E b and jEj = n. We give a new sweep-line algorithm that reports the k intersecting pairs of segments of E....
Elementary algorithms for reporting intersections of curve segments (1999)
Jean-daniel Boissonnat, Antoine Vigneron
Let E r and E b be two sets of x-monotone and non-intersecting curve segments, E = E r [ E b and jEj = n. We give a new sweep-line algorithm that reports the k intersecting pairs of segments of E....
Convex Tours of Bounded Curvature. (1999)
Boissonnat, Jean-Daniel, Czyzowicz, Jurek, Devillers, Olivier, Robert, Jean-Marc, Yvinec, Mariette
We consider the motion planning problem for a point constrained to move along a smooth closed convex path of bounded curvature. The workspace of the moving point is bounded by a convex polygon with m...
Convex Tours of Bounded Curvature. (1999)
Boissonnat, Jean-Daniel, Czyzowicz, Jurek, Devillers, Olivier, Robert, Jean-Marc, Yvinec, Mariette
We consider the motion planning problem for a point constrained to move along a smooth closed convex path of bounded curvature. The workspace of the moving point is bounded by a convex polygon with m...
Voronoi Diagrams in Higher Dimensions under Certain Polyhedral Distance Functions (1998)
Jean-daniel Boissonnat, Jean-daniel Boissonnat, Micha Sharir, Micha Sharir, Boaz Tagansky, Boaz Tagansky, ...
The paper bounds the combinatorial complexity of the Voronoi diagram of a set of points under certain polyhedral distance functions. Specifically, if S is a set of n points in general position in...
Voronoi Diagrams in Higher Dimensions under Certain Polyhedral Distance Functions (1998)
Jean-daniel Boissonnat, Micha Sharir, Boaz Tagansky, Mariette Yvinec
The paper bounds the combinatorial complexity of the Voronoi diagram of a set of points under certain polyhedral distance functions. Specifically, if S is a set of n points in general position in IR...
Efficient Algorithms for Line and Curve Segment Intersection Using Restricted Predicates (1998)
Jean-Daniel Boissonnat, Jack Snoeyink
We consider whether restricted sets of geometric primitives support efficient algorithms to solve line and curve segment intersection problems in the plane. Our restrictions are based on the notion...
Robust Plane Sweep for Intersecting Segments (1997)
Boissonnat, Jean-Daniel, Preparata, Franco P.
In this paper, we reexamine in the framework of robust computation the Bentley-Ottmann algorithm for reporting intersecting pairs of segments in the plane. This algorithm has been reported as being...
Motion Planning of Legged Robots (1997)
Boissonnat, Jean-Daniel, Devillers, Olivier, Lazard, Sylvain
We study the problem of computing the free space \Fsimple legged robot called the spider robot. The body of this robot is a single point and the legs are attached to the body. The robot is subject to...
Robust Plane Sweep for Intersecting Segments (1997)
Boissonnat, Jean-Daniel, Preparata, Franco P.
In this paper, we reexamine in the framework of robust computation the Bentley-Ottmann algorithm for reporting intersecting pairs of segments in the plane. This algorithm has been reported as being...
Motion Planning of Legged Robots (1997)
Boissonnat, Jean-Daniel, Devillers, Olivier, Lazard, Sylvain
We study the problem of computing the free space \Fsimple legged robot called the spider robot. The body of this robot is a single point and the legs are attached to the body. The robot is subject to...
Evaluating signs of determinants using single-precision arithmeti (1997)
Avnaim, Francis, Boissonnat, Jean-Daniel, Devillers, Olivier, Preparata, Franco, Yvinec, Mariette
We propose a method to evaluate signs of 2x2 and 3x3 determinants with b-bit integer entries using only b and (b+1)-bit arithmetic respectively. This algorithm has numerous applications in geometric...
Evaluating signs of determinants using single-precision arithmeti (1997)
Avnaim, Francis, Boissonnat, Jean-Daniel, Devillers, Olivier, Preparata, Franco, Yvinec, Mariette
We propose a method to evaluate signs of 2x2 and 3x3 determinants with b-bit integer entries using only b and (b+1)-bit arithmetic respectively. This algorithm has numerous applications in geometric...
Robust Plane Sweep for Intersecting Segments (1997)
Boissonnat, Jean-Daniel, Preparata, Franco P.
In this paper, we reexamine in the framework of robust computation the Bentley-Ottmann algorithm for reporting intersecting pairs of segments in the plane. This algorithm has been reported as being...
Motion Planning of Legged Robots (1997)
Boissonnat, Jean-Daniel, Devillers, Olivier, Lazard, Sylvain
We study the problem of computing the free space \Fsimple legged robot called the spider robot. The body of this robot is a single point and the legs are attached to the body. The robot is subject to...
Evaluating signs of determinants using single-precision arithmeti (1997)
Avnaim, Francis, Boissonnat, Jean-Daniel, Devillers, Olivier, Preparata, Franco, Yvinec, Mariette
We propose a method to evaluate signs of 2x2 and 3x3 determinants with b-bit integer entries using only b and (b+1)-bit arithmetic respectively. This algorithm has numerous applications in geometric...
Robust Plane Sweep for Intersecting Segments (1997)
Unit Inria, Sophia Antipolis, Jean-daniel Boissonnat, Jean-daniel Boissonnat, Franco P. Preparata, Franco P. Preparata
In this paper, we reexamine in the framework of robust computation the Bentley-Ottmann algorithm for reporting intersecting pairs of segments in the plane. This algorithm has been reported as being...
Evaluating Signs of Determinants Using Single-Precision Arithmetic (1997)
Jean-daniel Boissonnat, Francis Avnaim, Francis Avnaim, Olivier Devillers, Olivier Devillers, Franco P. Preparata, ...
We propose a method to evaluate signs of 2 × 2 and 3 × 3 determinants with b-bit integer entries using only b and (b + 1)-bit arithmetic respectively. This algorithm has numerous...
Minkowski Operations For Satellite Antenna Layout (1997)
Jean-daniel Boissonnat, Eelco De Lange, Monique Teillaud
Satellite layout is a very hard task because available space for the equipments is small and the physical constraints on the layout are strong. In this article, we show how some physical layout...
Robust plane sweep for intersecting segments (1997)
Jean-daniel Boissonnat, P. Preparata
Abstract. In this paper, we reexamine in the framework of robust computation the Bentley– Ottmann algorithm for reporting intersecting pairs of segments in the plane. This algorithm has been...
Reconstruction of Geological Structures from Heterogeneous and Sparse Data (1996)
Boissonnat, Jean-Daniel, Nullans, Stéphane
Given a set of sparse and heterogeneous outcrop and drilling data, we want to retrieve a complete and coherent model of the underground model, i.e. to determine the entire geometry of the surfaces...
Minkowski Operations for Satellite Antenna Layout (1996)
Boissonnat, Jean-Daniel, De Lange, Eelco, Teillaud, Monique
Satellite layout is a very hard task because available space for the equipments is small and the physical constraints on the layout are strong. In this article, we show how some physical layout...
Boissonnat, Jean-Daniel, Lazard, Sylvain
In this paper, we consider the problem of computing a shortest path of bounded curvature amidst obstacles in the plane. More precisely, given prescribed initial and final configurations (i.e....
Reconstruction of Geological Structures from Heterogeneous and Sparse Data (1996)
Boissonnat, Jean-Daniel, Nullans, Stéphane
Given a set of sparse and heterogeneous outcrop and drilling data, we want to retrieve a complete and coherent model of the underground model, i.e. to determine the entire geometry of the surfaces...
Minkowski Operations for Satellite Antenna Layout (1996)
Boissonnat, Jean-Daniel, De Lange, Eelco, Teillaud, Monique
Satellite layout is a very hard task because available space for the equipments is small and the physical constraints on the layout are strong. In this article, we show how some physical layout...
Boissonnat, Jean-Daniel, Lazard, Sylvain
In this paper, we consider the problem of computing a shortest path of bounded curvature amidst obstacles in the plane. More precisely, given prescribed initial and final configurations (i.e....
Reconstruction of Geological Structures from Heterogeneous and Sparse Data (1996)
Boissonnat, Jean-Daniel, Nullans, Stéphane
Given a set of sparse and heterogeneous outcrop and drilling data, we want to retrieve a complete and coherent model of the underground model, i.e. to determine the entire geometry of the surfaces...
Minkowski Operations for Satellite Antenna Layout (1996)
Boissonnat, Jean-Daniel, De Lange, Eelco, Teillaud, Monique
Satellite layout is a very hard task because available space for the equipments is small and the physical constraints on the layout are strong. In this article, we show how some physical layout...
Boissonnat, Jean-Daniel, Lazard, Sylvain
In this paper, we consider the problem of computing a shortest path of bounded curvature amidst obstacles in the plane. More precisely, given prescribed initial and final configurations (i.e....
Minkowski Operations For Satellite Antenna Layout (1996)
Jean-daniel Boissonnat, Jean-daniel Boissonnat, Eelco De Lange, Eelco De Lange, Monique Teillaud, Monique Teillaud
Satellite layout is a very hard task because available space for the equipments is small and the physical constraints on the layout are strong. In this article, we show how some physical layout...
Reconstruction of Geological Structures from Heterogeneous and Sparse Data (1996)
Stephane Nullans, Jean-daniel Boissonnat, Jean-daniel Boissonnat
Given a set of sparse and heterogeneous outcrop and drilling data, we want to retrieve a complete and coherent model of the underground model, i.e. to determine the entire geometry of the surfaces...
Reconstruction of Geological Structures from Heterogeneous and Sparse Data (1996)
Jean-daniel Boissonnat, Stéphane Nullans
Given a set of sparse and heterogeneous outcrop and drilling data, we want to retrieve a complete and coherent model of the underground model, i.e. to determine the entire geometry of the surfaces...
On Computing Four-Finger Equilibrium and Force-Closure Grasps of Polyhedral Objects (1996)
Jean Ponce, Steve Sullivan, Attawith Sudsang, Jean-daniel Boissonnat, Jean-Pierre Merlet
: This paper addresses the problem of computing stable grasps of three-dimensional polyhedral objects. We consider the case of a hand equipped with four hard fingers and assume point contact with...
Computing Largest Circles Separating Two Sets of Segments (1996)
Jean-daniel Boissonnat, Jurek Czyzowicz, Olivier Devillers, Joge Urrutia, Mariette Yvinec
A circle C separates two planar sets if it en closes one of the sets and its open interior disk does not meet the other set. A separating circle is a largest one if it cannot be locally increased...
An Algorithm for Constructing the Convex Hull of a Set of Spheres in Dimension d (1996)
Boissonnat, Jean-Daniel, Cerezo, André, Devillers, Olivier, Duquesne, Jacqueline, Yvinec, Mariette
We present an algorithm which computes the convex hull of a set of spheres in dimension d in time O(n^ceil(d/2)+n log n). It is worst case optimal in three dimensions and in even dimensions. The same...
An Algorithm for Constructing the Convex Hull of a Set of Spheres in Dimension d (1996)
Boissonnat, Jean-Daniel, Cerezo, André, Devillers, Olivier, Duquesne, Jacqueline, Yvinec, Mariette
We present an algorithm which computes the convex hull of a set of spheres in dimension d in time O(n^ceil(d/2)+n log n). It is worst case optimal in three dimensions and in even dimensions. The same...
Computing Largest Circles Separating Two Sets of Segments (1995)
Boissonnat, Jean-Daniel, Czyzowicz, Jurek, Devillers, Olivier, Urrutia, Jorge, Yvinec, Mariette
A circle $C$ separates two planar sets if it encloses one of the sets and its open interior disk does not meet the other set. A separating circle is a largest one if it cannot be locally increased...
Voronoi Diagrams in Higher Dimensions under Certain Polyhedral Distance Functions (1995)
Boissonnat, Jean-Daniel, Sharir, Micha, Tagansky, Boaz, Yvinec, Mariette
The paper bounds the combinatorial complexity of the Voronoi diagram of a set of points under certain polyhedral distance functions. Specifically, if $ß$ is a set of $n$ points in general position...
Computing Largest Circles Separating Two Sets of Segments (1995)
Boissonnat, Jean-Daniel, Czyzowicz, Jurek, Devillers, Olivier, Urrutia, Jorge, Yvinec, Mariette
A circle $C$ separates two planar sets if it encloses one of the sets and its open interior disk does not meet the other set. A separating circle is a largest one if it cannot be locally increased...
Voronoi Diagrams in Higher Dimensions under Certain Polyhedral Distance Functions (1995)
Boissonnat, Jean-Daniel, Sharir, Micha, Tagansky, Boaz, Yvinec, Mariette
The paper bounds the combinatorial complexity of the Voronoi diagram of a set of points under certain polyhedral distance functions. Specifically, if $ß$ is a set of $n$ points in general position...
Computing Largest Circles Separating Two Sets of Segments (1995)
Boissonnat, Jean-Daniel, Czyzowicz, Jurek, Devillers, Olivier, Urrutia, Jorge, Yvinec, Mariette
A circle $C$ separates two planar sets if it encloses one of the sets and its open interior disk does not meet the other set. A separating circle is a largest one if it cannot be locally increased...
Voronoi Diagrams in Higher Dimensions under Certain Polyhedral Distance Functions (1995)
Boissonnat, Jean-Daniel, Sharir, Micha, Tagansky, Boaz, Yvinec, Mariette
The paper bounds the combinatorial complexity of the Voronoi diagram of a set of points under certain polyhedral distance functions. Specifically, if $ß$ is a set of $n$ points in general position...
Computing Largest Circles Separating Two Sets of Segments (1995)
Jorge Urrutia, Jean-daniel Boissonnat, Jean-daniel Boissonnat, Jurek Czyzowicz, Jurek Czyzowicz, Olivier Devillers, ...
A circle C separates two planar sets if it encloses one of the sets and its open interior disk does not meet the other set. A separating circle is a largest one if it cannot be locally increased...
Circular Separability of Polygons (1995)
Mariette Yvinec, Jean-daniel Boissonnat, Jean-daniel Boissonnat, Jurek Czyzowicz, Jurek Czyzowicz, Olivier Devillers, ...
Two planar sets are circularly separable if there exists a circle enclosing one of the set and whose open interior disk does not intersect the other set. This paper studies two problems related to...
Computing Largest Circles Separating Two Sets of Segments (1995)
Jorge Urrutia, Jean-daniel Boissonnat, Jean-daniel Boissonnat, Jurek Czyzowicz, Jurek Czyzowicz, ...
A circle C separates two planar sets if it encloses one of the sets and its open interior disk does not meet the other set. A separating circle is a largest one if it cannot be locally increased...
Convex Tours of Bounded Curvature (1994)
Boissonnat, Jean-Daniel, Czyzowicz, Jurek, Devillers, Olivier, Robert, Jean-Marc, Yvinec, Mariette
We consider the motion planning problem for a point constrained to move along a smooth closed convex path of bounded curvature. The workspace of the moving point is bounded by a convex polygon with...
Circular Separability of Polygons (1994)
Boissonnat, Jean-Daniel, Czyzowicz, Jurek, Devillers, Olivier, Yvinec, Mariette
Two planar sets are circularly separable if there exists a circle enclosing one of the set and whose open interior disk does not intersect the other set. This paper studies two problems related to...
Evaluating signs of determinants using single-precision arithmetic (1994)
Avnaim, Francis, Boissonnat, Jean-Daniel, Devillers, Olivier, Preparata, Franco P., Yvinec, Mariette
We propose a method to evaluate signs of $2\times 2$ and $3\times 3$ determinants with $b$-bit integer entries using only $b$ and $(b+1)$-bit arithmetic respectively. This algorithm has numerous...
The Shortest path synthesis for non-holonomic robots moving forwards (1994)
Bui, X.N., Soueres, P., Boissonnat, Jean-Daniel, Laumond, J.P.
Convex Tours of Bounded Curvature (1994)
Boissonnat, Jean-Daniel, Czyzowicz, Jurek, Devillers, Olivier, Robert, Jean-Marc, Yvinec, Mariette
We consider the motion planning problem for a point constrained to move along a smooth closed convex path of bounded curvature. The workspace of the moving point is bounded by a convex polygon with...
Circular Separability of Polygons (1994)
Boissonnat, Jean-Daniel, Czyzowicz, Jurek, Devillers, Olivier, Yvinec, Mariette
Two planar sets are circularly separable if there exists a circle enclosing one of the set and whose open interior disk does not intersect the other set. This paper studies two problems related to...
Evaluating signs of determinants using single-precision arithmetic (1994)
Avnaim, Francis, Boissonnat, Jean-Daniel, Devillers, Olivier, Preparata, Franco P., Yvinec, Mariette
We propose a method to evaluate signs of $2\times 2$ and $3\times 3$ determinants with $b$-bit integer entries using only $b$ and $(b+1)$-bit arithmetic respectively. This algorithm has numerous...
The Shortest path synthesis for non-holonomic robots moving forwards (1994)
Bui, Xuân-Nam, Soueres, Philippe, Boissonnat, Jean-Daniel, Laumond, Jean-Paul
Disponible dans les fichiers attachés à ce document
Boissonnat, Jean-Daniel, Cerezo, André, Leblond, Juliette
Disponible dans les fichiers attachés à ce document
Accessibility region for a car that only moves forwards along optimal paths (1994)
Bui, Xuân-Nam, Boissonnat, Jean-Daniel
Disponible dans les fichiers attachés à ce document
Convex Tours of Bounded Curvature (1994)
Boissonnat, Jean-Daniel, Czyzowicz, Jurek, Devillers, Olivier, Robert, Jean-Marc, Yvinec, Mariette
We consider the motion planning problem for a point constrained to move along a smooth closed convex path of bounded curvature. The workspace of the moving point is bounded by a convex polygon with...
Circular Separability of Polygons (1994)
Boissonnat, Jean-Daniel, Czyzowicz, Jurek, Devillers, Olivier, Yvinec, Mariette
Two planar sets are circularly separable if there exists a circle enclosing one of the set and whose open interior disk does not intersect the other set. This paper studies two problems related to...
Evaluating signs of determinants using single-precision arithmetic (1994)
Avnaim, Francis, Boissonnat, Jean-Daniel, Devillers, Olivier, Preparata, Franco P., Yvinec, Mariette
We propose a method to evaluate signs of $2\times 2$ and $3\times 3$ determinants with $b$-bit integer entries using only $b$ and $(b+1)$-bit arithmetic respectively. This algorithm has numerous...
The Shortest path synthesis for non-holonomic robots moving forwards (1994)
Bui, Xuân-Nam, Soueres, Philippe, Boissonnat, Jean-Daniel, Laumond, Jean-Paul
Disponible dans les fichiers attachés à ce document
Boissonnat, Jean-Daniel, Cerezo, André, Leblond, Juliette
Disponible dans les fichiers attachés à ce document
Accessibility region for a car that only moves forwards along optimal paths (1994)
Bui, Xuân-Nam, Boissonnat, Jean-Daniel
Disponible dans les fichiers attachés à ce document
Convex tours of bounded curvature (1994)
Jean-daniel Boissonnat, Jurek Czyzowicz, Olivier Devillers, Jean-marc Robert, Mariette Yvinec
We consider the motion planning problem for a point constrained to move along a smooth closed convex path of bounded curvature. The workspace of the moving point is bounded by a convex polygon with m...
Convex Tours of Bounded Curvature (1994)
Jean-daniel Boissonnat, Jean-daniel Boissonnat, Jurek Czyzowicz, Jurek Czyzowicz, Olivier Devillers, Olivier Devillers, ...
We consider the motion planning problem for a point constrained to move along a smooth closed convex path of bounded curvature. The workspace of the moving point is bounded by a convex polygon with m...
Andre Cerezo, Jean-daniel Boissonnat, Juliette Leblond, Juliette Leblond, Programme Robotique, ...
: We consider the class of C 2 , piecewise C 3 , planar paths joining two given configurations (position, orientation, and curvature) X 0 and X f , and along which the derivative of the curvature...
Convex tours of bounded curvature (1994)
Apport De Recherche, Jean-daniel Boissonnat, Jean-daniel Boissonnat, Jurek Czyzowicz, Jurek Czyzowicz, Olivier Devillers, ...
We consider the motion planning problem for a point constrained to move along a smooth closed convex path of bounded curvature. The workspace of the moving point is bounded by a convex polygon with m...
An Algorithm for constructing the convex hull of a set of spheres in dimension d (1993)
Boissonnat, Jean-Daniel, Cerezo, A., Devillers, Olivier, Duquesne, Jacqueline, Yvinec, Mariette
On-line randomized construction of the upper envelope of triangles and surface patches in R3 (1993)
Boissonnat, Jean-Daniel, Dobrindt, Katrin
In this paper we describe an on-line randomized algorithm for computing the upper envelope (i.e. poinwise maximum) of a set of n triangles in three dimensions. The main new feature of this algorithm...
An Algorithm for constructing the convex hull of a set of spheres in dimension d (1993)
Boissonnat, Jean-Daniel, Cerezo, André, Devillers, Olivier, Duquesne, Jacqueline, Yvinec, Mariette
Disponible dans les fichiers attachés à ce document
On-line randomized construction of the upper envelope of triangles and surface patches in R3 (1993)
Boissonnat, Jean-Daniel, Dobrindt, Katrin
In this paper we describe an on-line randomized algorithm for computing the upper envelope (i.e. poinwise maximum) of a set of n triangles in three dimensions. The main new feature of this algorithm...
A semidynamic construction of higher-order {Voronoi} diagrams and its randomized analysis (1993)
Boissonnat, Jean-Daniel, Devillers, Olivier, Teillaud, Monique
Thek-Delaunay tree extends the Delaunay tree introduced in [1], and [2]. It is a hierarchical data structure that allows the semidynamic construction of the higher-order Voronoi diagrams of a finite...
A semidynamic construction of higher-order {Voronoi} diagrams and its randomized analysis (1993)
Boissonnat, Jean-Daniel, Devillers, Olivier, Teillaud, Monique
Thek-Delaunay tree extends the Delaunay tree introduced in [1], and [2]. It is a hierarchical data structure that allows the semidynamic construction of the higher-order Voronoi diagrams of a finite...
An Algorithm for constructing the convex hull of a set of spheres in dimension d (1993)
Boissonnat, Jean-Daniel, Cerezo, André, Devillers, Olivier, Duquesne, Jacqueline, Yvinec, Mariette
Disponible dans les fichiers attachés à ce document
On-line randomized construction of the upper envelope of triangles and surface patches in R3 (1993)
Boissonnat, Jean-Daniel, Dobrindt, Katrin
In this paper we describe an on-line randomized algorithm for computing the upper envelope (i.e. poinwise maximum) of a set of n triangles in three dimensions. The main new feature of this algorithm...
A semidynamic construction of higher-order {Voronoi} diagrams and its randomized analysis (1993)
Boissonnat, Jean-Daniel, Devillers, Olivier, Teillaud, Monique
Thek-Delaunay tree extends the Delaunay tree introduced in [1], and [2]. It is a hierarchical data structure that allows the semidynamic construction of the higher-order Voronoi diagrams of a finite...
The Shortest Path Synthesis for Non-holonomic Robots Moving Forwards (1993)
Xuân-Nam Bui, Philippe Souères, Jean-daniel Boissonnat, Jean-daniel Boissonnat, ...
: We calculate the partition of the configuration space IR 2 \Theta S 1 of a car-like robot, only moving forwards, with respect to the type of the length optimal paths. This kind of robot is subject...
Motion planning of legged robots : the spider robot problem (1992)
Boissonnat, Jean-Daniel, Devillers, Olivier, Preparata, Franco P., Donati, L.
We consider the problem of planning motions of a simple legged robot called the spider robot. The robot is modelled as a point where all its legs are attached, and the footholds where the robot can...
Three dimensional reconstruction of complex shapes based on the Delaunay triangulation (1992)
Boissonnat, Jean-Daniel, Geiger, B.
We propose a solution to the problem of 3D reconstruction from cross sections, based on the Delaunay triangulation of object contours. Its properties-especially the close relationship to the medial...
Motion planning of legged robots : the spider robot problem (1992)
Boissonnat, Jean-Daniel, Devillers, Olivier, Preparata, Franco P., Donati, Leonbattista
We consider the problem of planning motions of a simple legged robot called the spider robot. The robot is modelled as a point where all its legs are attached, and the footholds where the robot can...
Three dimensional reconstruction of complex shapes based on the Delaunay triangulation (1992)
Boissonnat, Jean-Daniel, Geiger, Bernhard
We propose a solution to the problem of 3D reconstruction from cross sections, based on the Delaunay triangulation of object contours. Its properties-especially the close relationship to the medial...
Applications of random sampling to on-line algorithms in computational geometry (1992)
Boissonnat, Jean-Daniel, Devillers, Olivier, Schott, René, Teillaud, Monique, Yvinec, Mariette
This paper presents a general framework for the design and randomized analysis of geometric algorithms. These algorithms are on-line and the framework provides general bounds for their expected space...
Applications of random sampling to on-line algorithms in computational geometry (1992)
Boissonnat, Jean-Daniel, Devillers, Olivier, Schott, René, Teillaud, Monique, Yvinec, Mariette
This paper presents a general framework for the design and randomized analysis of geometric algorithms. These algorithms are on-line and the framework provides general bounds for their expected space...
Motion planning of legged robots : the spider robot problem (1992)
Boissonnat, Jean-Daniel, Devillers, Olivier, Preparata, Franco P., Donati, Leonbattista
We consider the problem of planning motions of a simple legged robot called the spider robot. The robot is modelled as a point where all its legs are attached, and the footholds where the robot can...
Three dimensional reconstruction of complex shapes based on the Delaunay triangulation (1992)
Boissonnat, Jean-Daniel, Geiger, Bernhard
We propose a solution to the problem of 3D reconstruction from cross sections, based on the Delaunay triangulation of object contours. Its properties-especially the close relationship to the medial...
Applications of random sampling to on-line algorithms in computational geometry (1992)
Boissonnat, Jean-Daniel, Devillers, Olivier, Schott, René, Teillaud, Monique, Yvinec, Mariette
This paper presents a general framework for the design and randomized analysis of geometric algorithms. These algorithms are on-line and the framework provides general bounds for their expected space...
Applications of random sampling to on-line algorithms in computational geometry (1992)
Jean-daniel Boissonnat, Olivier Devillerst, Ren Schott, Monique Teillaud, Mariette Yvinecs
Application de l'chantillonage alatoire aux algorithmes gomtriques en ligne
Motion Planning of Legged Robots: The Spider Robot Problem (1992)
E De Recherche, Route Des Lucioles, Jean-daniel Boissonnat, Jean-daniel Boissonnat, Olivier Devillers, Olivier Devillers, ...
We consider the problem of planning motions of a simple legged robot called the spider robot. The robot is modelled as a point where all its legs are attached, and the footholds where the robot can...
Output sensitive construction of the 3D Delaunay triangulation of constrained sets of points (1991)
Boissonnat, Jean-Daniel, Cerezo, A., Devillers, Olivier, Teillaud, Monique
Shortest path of bounded curvature in the plane (1991)
Boissonnat, Jean-Daniel, Cerezo, André, Leblond, Juliette
Disponible dans les fichiers attachés à ce document
Output sensitive construction of the 3D Delaunay triangulation of constrained sets of points (1991)
Boissonnat, Jean-Daniel, Cerezo, André, Devillers, Olivier, Teillaud, Monique
Disponible dans les fichiers attachés à document
Shortest path of bounded curvature in the plane (1991)
Boissonnat, Jean-Daniel, Cerezo, André, Leblond, Juliette
Disponible dans les fichiers attachés à ce document
Output sensitive construction of the 3D Delaunay triangulation of constrained sets of points (1991)
Boissonnat, Jean-Daniel, Cerezo, André, Devillers, Olivier, Teillaud, Monique
Disponible dans les fichiers attachés à document
Computing the Union of 3-Colored Triangles (1991)
Boissonnat, Jean-Daniel, Devillers, Olivier, Preparata, Franco
Given is a set \s\ of $n$ points, each colored with one of $k \geq 3$ colours. We say that a triangle defined by three points of \s\ is 3-colored if its vertices have distinct colours. We prove in...
Computing the Union of 3-Colored Triangles (1991)
Boissonnat, Jean-Daniel, Devillers, Olivier, Preparata, Franco
Given is a set \s\ of $n$ points, each colored with one of $k \geq 3$ colours. We say that a triangle defined by three points of \s\ is 3-colored if its vertices have distinct colours. We prove in...
Computing the union of 3-colored triangles (1991)
Jean-daniel Boissonnat, Olivier Devillers, Franco P. Preparata
Given is a set S of n points, each colored with one of k 3 colours. We say that a triangle defined by three points of S is 3-colored if its vertices have distinct colours. We prove in this paper that...
Computing The Union Of 3-Colored Triangles (1991)
Jean-daniel Boissonnat, Olivier Devillers, Franco P. Preparata
Given is a set S of n points, each colored with one of k 3 colours. We say that a triangle defined by three points of S is 3-colored if its vertices have distinct colours. We prove in this paper that...
On The Randomized Construction Of The Delaunay Tree (1991)
E De Recherche, En Informatique, Et En Automatique, Sophia Antipolis, Jean-daniel Boissonnat, Jean-daniel Boissonnat, ...
The Delaunay Tree is a hierarchical data structure that was introduced in [BT86]. It is defined from the Delaunay triangulation and, roughly speaking, represents a triangulation as a hierarchy of...
Computing the union of 3-colored triangles (1990)
Boissonnat, Jean-Daniel, Devillers, Olivier, Preparata, Franco P.
Applications of random sampling to on-line algorithms in computational geometry (1990)
Boissonnat, Jean-Daniel, Devillers, Olivier, Schott, Rene, Teillaud, Monique, Yvinec, Mariette
A dynamic construction of higher order Voronoi diagrams and its randomized analysis (1990)
Boissonnat, Jean-Daniel, Devillers, Olivier, Teillaud, Monique
O(kd+2n ë[??]õlog n) et une place memoire O(kd+1n ë[??]õlog n). L'algorithme est simple et des resultats experimentaux sont presentes.
Computing the union of 3-colored triangles (1990)
Boissonnat, Jean-Daniel, Devillers, Olivier, Preparata, Franco P.
Disponible dans les fichiers attachés à ce document
Applications of random sampling to on-line algorithms in computational geometry (1990)
Boissonnat, Jean-Daniel, Devillers, Olivier, Schott, Rene, Teillaud, Monique, Yvinec, Mariette
Disponible dans les fichiers attachés à ce document
A dynamic construction of higher order Voronoi diagrams and its randomized analysis (1990)
Boissonnat, Jean-Daniel, Devillers, Olivier, Teillaud, Monique
Disponible dans les fichiers attachés à ce document
Computing the union of 3-colored triangles (1990)
Boissonnat, Jean-Daniel, Devillers, Olivier, Preparata, Franco P.
Disponible dans les fichiers attachés à ce document
Applications of random sampling to on-line algorithms in computational geometry (1990)
Boissonnat, Jean-Daniel, Devillers, Olivier, Schott, Rene, Teillaud, Monique, Yvinec, Mariette
Disponible dans les fichiers attachés à ce document
A dynamic construction of higher order Voronoi diagrams and its randomized analysis (1990)
Boissonnat, Jean-Daniel, Devillers, Olivier, Teillaud, Monique
Disponible dans les fichiers attachés à ce document
On the randomized construction of the Delaunay tree (1989)
Boissonnat, Jean-Daniel, Devillers-Teillaud, M.
The Delaunay is a hierarchical data structure that has been introduced. The Delaunay tree is defined from the Delaunay triangulation and, roughly speaking, represents a triangulation as a hierarchy...
Probing a scene of non convex polyhedra (1989)
Boissonnat, Jean-Daniel, Yvinec, Mariette
We show, in this paper, how one can compute the exact shapes of a class of polyhedral scenes by means of a simple sensory device issuing probes. A scene in this class consists of disjoint polyhedra...
On the randomized construction of the Delaunay tree (1989)
Boissonnat, Jean-Daniel, Teillaud, Monique
The Delaunay is a hierarchical data structure that has been introduced. The Delaunay tree is defined from the Delaunay triangulation and, roughly speaking, represents a triangulation as a hierarchy...
Probing a scene of non convex polyhedra (1989)
Boissonnat, Jean-Daniel, Yvinec, Mariette
We show, in this paper, how one can compute the exact shapes of a class of polyhedral scenes by means of a simple sensory device issuing probes. A scene in this class consists of disjoint polyhedra...
On the randomized construction of the Delaunay tree (1989)
Boissonnat, Jean-Daniel, Teillaud, Monique
The Delaunay is a hierarchical data structure that has been introduced. The Delaunay tree is defined from the Delaunay triangulation and, roughly speaking, represents a triangulation as a hierarchy...
Probing a scene of non convex polyhedra (1989)
Boissonnat, Jean-Daniel, Yvinec, Mariette
We show, in this paper, how one can compute the exact shapes of a class of polyhedral scenes by means of a simple sensory device issuing probes. A scene in this class consists of disjoint polyhedra...
On the order induced by a set of rays. Application to the probing of non convex polygons (1988)
Alevizos, Panagiotis, Boissonnat, Jean-Daniel, Yvinec, Mariette
Disponible dans les fichiers attachés à ce document
On the boundary of a union of rays (1988)
Alevizos, Panagiotis, Boissonnat, Jean-Daniel, Preparata, Franco P.
Disponible dans les fichiers attachés à ce document
Polygon placement under translation and rotation (1988)
Boissonnat, Jean-Daniel, Avnaim, Francis
Disponible dans les fichiers attachés à ce document
A practical exact motion planning algorithm for polygonal objects amidst polygonal obstacles (1988)
Boissonnat, Jean-Daniel, Faverjon, Bernard, Avnaim, Francis
Disponible dans les fichiers attachés à ce document
On the order induced by a set of rays. Application to the probing of non convex polygons (1988)
Alevizos, Panagiotis, Boissonnat, Jean-Daniel, Yvinec, Mariette
Disponible dans les fichiers attachés à ce document
On the boundary of a union of rays (1988)
Alevizos, Panagiotis, Boissonnat, Jean-Daniel, Preparata, Franco P.
Disponible dans les fichiers attachés à ce document
Polygon placement under translation and rotation (1988)
Boissonnat, Jean-Daniel, Avnaim, Francis
Disponible dans les fichiers attachés à ce document
A practical exact motion planning algorithm for polygonal objects amidst polygonal obstacles (1988)
Boissonnat, Jean-Daniel, Faverjon, Bernard, Avnaim, Francis
Disponible dans les fichiers attachés à ce document
On the external boundary of a union of rays* (1987)
Boissonnat, Jean-Daniel, Preparata, Franco P.
Disponible dans les fichiers attachés à ce document
Placement simultane en translation (1987)
Boissonnat, Jean-Daniel, Avnaim, Francis
Disponible dans les fichiers attachés à ce document
On the external boundary of a union of rays* (1987)
Boissonnat, Jean-Daniel, Preparata, Franco P.
Disponible dans les fichiers attachés à ce document
Placement simultane en translation (1987)
Boissonnat, Jean-Daniel, Avnaim, Francis
Disponible dans les fichiers attachés à ce document