Olivier Devillers

Filtering Relocations on a Delaunay Triangulation (2009)

This paper considers the problem of updating efficiently a Delaunay triangulation when vertices are moving under small perturbations. Its main contribution is a set of algorithms based on the concept...

Tournois, Jane, Alliez, Pierre, Devillers, Olivier

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

Fast Delaunay Triangulation for Converging Point Relocation Sequences (2009)

On the Complexity of Umbra and Penumbra (2009)

This paper considers the problem of updating efficiently a Delaunay triangulation when vertices are moving under small perturbations. Its main contribution is a set of algorithms based on the concept...

Demouth, Julien, Devillers, Olivier, Everett, Hazel, Glisse, Marc, Lazard, Sylvain, Seidel, Raimund

Computing shadow boundaries is a difficult problem in the case of non-point light sources. A point is in the umbra if it does not see any part of any light source; it is in full light if it sees...

On the Complexity of Umbra and Penumbra (2009)

Demouth, Julien, Devillers, Olivier, Everett, Hazel, Glisse, Marc, Lazard, Sylvain, Seidel, Raimund

Computing shadow boundaries is a difficult problem in the case of non-point light sources. A point is in the umbra if it does not see any part of any light source; it is in full light if it sees...

Vertex Removal in Two Dimensional Delaunay Triangulation: Asymptotic Complexity is Pointless (2009)

Vertex Removal in Two Dimensional Delaunay Triangulation: Asymptotic Complexity is Pointless (2009)

The theoretical complexity of vertex removal in a Delaunay triangulation is often given in terms of the degree d of the removed point with usual results O(d), O(d log d), or O(d²). In fact the...

Randomisation, sphères et déplacements de robots (2008)

The theoretical complexity of vertex removal in a Delaunay triangulation is often given in terms of the degree d of the removed point with usual results O(d), O(d log d), or O(d²). In fact the...

A Tight Bound for the Delaunay Triangulation of Points on a Polyhedron (2008)

Ce mémoire d'habilitation présente 14 articles différents, structurés en trois parties : algorithmes randomisés, algorithmes sur les sphères et placements de robots. Les algorithmes randomisés...

Amenta, Nina, Attali, Dominique, Devillers, Olivier

We show that the Delaunay triangulation of a set of n points distributed nearly uniformly on a p-dimensional polyhedron (not necessarily convex) in d-dimensional Euclidean space is O(n^((d-k+1)/p)),...

A Tight Bound for the Delaunay Triangulation of Points on a Polyhedron (2008)

Amenta, Nina, Attali, Dominique, Devillers, Olivier

We show that the Delaunay triangulation of a set of n points distributed nearly uniformly on a p-dimensional polyhedron (not necessarily convex) in d-dimensional Euclidean space is O(n^((d-k+1)/p)),...

Où y a-t-il de la géométrie algorithmique dans les réseaux ? C'est la question qui est posée ici, ou, plus exactement, les connaissances en géométrie algorithmique peuvent-elles apporter un...

published in Algorithmica 30, 2001, p.67–82. Circular Separability of Polygons ∗ (2008)

Où y a-t-il de la géométrie algorithmique dans les réseaux ? C'est la question qui est posée ici, ou, plus exactement, les connaissances en géométrie algorithmique peuvent-elles apporter un...

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

Abstract Perturbations and Vertex Removal (2008)

Olivier Devillers, Monique Teillaud

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

Interleaving Delaunay Refinement and Optimization for 2D Triangle Mesh Generation, in "Meshing Roundtable conference proceedings (2008)

Jane Tournois, Pierre Alliez, Olivier Devillers

Summary. We address the problem of generating 2D quality triangle meshes from a set of constraints provided as a planar straight line graph. The algorithm first computes a constrained Delaunay...

Abstract Maintaining Visibility Information of Planar Point Sets with a Moving Viewpoint (2008)

Olivier Devillers, Vida Dujmović, Hazel Everett, Samuel Hornus, Sue Whitesides

Given a set of n points in the plane, we consider the problem of computing the circular ordering of the points about a viewpoint q and efficiently maintaining this ordering information as q moves. 1

Between umbra and penumbra (2008)

Julien Demouth, Olivier Devillers, Hazel Everett, Sylvain Lazard, Raimund Seidel

Computing shadow boundaries is a difficult problem in the case of non-point light sources. A point is in the umbra if it does not see any part of any light source; it is in full light if it sees...

Computing a Single Cell in the Overlay of two Simple Polygons? (2008)

Mark Berg, Olivier Devillers, Katrin Dobrindt, Otfried Schwarzkopf A

This note combines the lazy randomized incremental construction scheme with the technique of \connectivity acceleration " to obtain an O(n(log? n) 2) time randomized algorithm to compute a...

On Circular Cylinders through Four or Five Points in Space (2008)

Olivier Devillers, Bernard Mourrain, Franco P. Preparata, Philippe Trebuchet

this paper is the analysis of circular cylinders through sets of points in three dimensions. This investigation has a number of motivations. Clearly, if a cylinder of radius R and direction t passes...

Simplification De Maillages Surfaciques (2008)

Programmation Gnrique Dans, Olivier Devillers

n d'arte [5]. L'implantation dans la bibliothque CGAL comprend plusieurs volets, dont la rdaction d'une documentation en anglais et le dveloppement d'une suite automatise de...

The Shuffling Buffer (2008)

Olivier Devillers, Philippe Guigue

The classical approach of computational geometry is the search for algorithms having the best possbile worst case complexity, unfortunately...

Empty-ellipse graphs (2008)

Devillers, Olivier, Erickson, Jeff, Goaoc, Xavier

We define and study a geometric graph over points in the plane that captures the local behavior of Delaunay triangulations of points on smooth surfaces in 3-space. Two points in a planar point set P...

Empty-ellipse graphs (2008)

Devillers, Olivier, Erickson, Jeff, Goaoc, Xavier

We define and study a geometric graph over points in the plane that captures the local behavior of Delaunay triangulations of points on smooth surfaces in 3-space. Two points in a planar point set P...

Où y a-t-il de la géométrie algorithmique dans les réseaux ? C'est la question qui est posée ici, ou, plus exactement, les connaissances en géométrie algorithmique peuvent-elles apporter un...

A Tight Bound for the Delaunay Triangulation of Points on a Polyhedron (2008)

Où y a-t-il de la géométrie algorithmique dans les réseaux ? C'est la question qui est posée ici, ou, plus exactement, les connaissances en géométrie algorithmique peuvent-elles apporter un...

Amenta, Nina, Attali, Dominique, Devillers, Olivier

We show that the Delaunay triangulation of a set of n points distributed nearly uniformly on a p-dimensional polyhedron (not necessarily convex) in d-dimensional Euclidean space is O(n^((d-k+1)/p)),...

A Tight Bound for the Delaunay Triangulation of Points on a Polyhedron (2008)

Amenta, Nina, Attali, Dominique, Devillers, Olivier

We show that the Delaunay triangulation of a set of n points distributed nearly uniformly on a p-dimensional polyhedron (not necessarily convex) in d-dimensional Euclidean space is O(n^((d-k+1)/p)),...

State of the Art: Updating Delaunay Triangulations for Moving Points (2008)

State of the Art: Updating Delaunay Triangulations for Moving Points (2008)

This paper considers the problem of updating efficiently a two-dimensional Delaunay triangulation when vertices are moving. We investigate the three current state-of-the-art approaches to solve this...

Helly-type theorems for approximate covering (2008)

This paper considers the problem of updating efficiently a two-dimensional Delaunay triangulation when vertices are moving. We investigate the three current state-of-the-art approaches to solve this...

Demouth, Julien, Devillers, Olivier, Glisse, Marc, Goaoc, Xavier

Let F \cup {U} be a collection of convex sets in R^d such that F covers U. We prove that if the elements of F and U have comparable size then a small subset of F suffices to cover most of the volume...

Helly-type theorems for approximate covering (2008)

Demouth, Julien, Devillers, Olivier, Glisse, Marc, Goaoc, Xavier

Let F \cup {U} be a collection of convex sets in R^d such that F covers U. We prove that if the elements of F and U have comparable size then a small subset of F suffices to cover most of the volume...

Predicates for line transversals to lines and line segments in three-dimensional space (2008)

Devillers, Olivier, Glisse, Marc, Lazard, Sylvain

When an observer is in a 3D scene, a topological change in the view arises when the line of sight is tangent to four objects. If we consider polyhedral scenes, the relevant lines of sight are...

Predicates for line transversals to lines and line segments in three-dimensional space (2008)

Devillers, Olivier, Glisse, Marc, Lazard, Sylvain

When an observer is in a 3D scene, a topological change in the view arises when the line of sight is tangent to four objects. If we consider polyhedral scenes, the relevant lines of sight are...

Succinct representations of planar maps (2008)

Castelli Aleardi, Luca, Devillers, Olivier, Schaeffer, Gilles

This paper addresses the problem of representing the connectivity information of geometric objects, using as little memory as possible. As opposed to raw compression issues, the focus here is on...

Succinct representations of planar maps (2008)

Castelli Aleardi, Luca, Devillers, Olivier, Schaeffer, Gilles

This paper addresses the problem of representing the connectivity information of geometric objects, using as little memory as possible. As opposed to raw compression issues, the focus here is on...

Counting Quadrics and Delaunay Triangulations and a new Convex Hull Theorem (2008)

Aicholzer, Oswin, Devillers, Olivier, Aurenhammer, Franz, Hackl, Thomas, Teillaud, Monique, Vogtenhuber, Birgit

Given a set $\cal S$ of $n$ points in three dimensions, we study the maximum numbers of quadrics spanned by subsets of points in $\cal S$ in various ways. We prove that the set of empty or enclosing...

Counting Quadrics and Delaunay Triangulations and a new Convex Hull Theorem (2008)

Aicholzer, Oswin, Devillers, Olivier, Aurenhammer, Franz, Hackl, Thomas, Teillaud, Monique, Vogtenhuber, Birgit

Given a set $\cal S$ of $n$ points in three dimensions, we study the maximum numbers of quadrics spanned by subsets of points in $\cal S$ in various ways. We prove that the set of empty or enclosing...

Delaunay Triangulations for Moving Points (2008)

Delaunay Triangulations for Moving Points (2008)

This paper considers the problem of updating efficiently a Delaunay triangulation when vertices are moving under small perturbations. Its main contribution is a set of algorithms based on the concept...

Empty-Ellipse Graphs (2008)

This paper considers the problem of updating efficiently a Delaunay triangulation when vertices are moving under small perturbations. Its main contribution is a set of algorithms based on the concept...

Olivier Devillers, Jeff Erickson, Xavier Goaoc

We define and study a geometric graph over points in the plane that captures the local behavior of Delaunay triangulations of points on smooth surfaces in IR 3. Two points in a planar point set P are...

a;2 (2007)

Mark De Berg, Olivier Devillers, Katrin Dobrindt, Otfried Schwarzkopf

b;1

Published in Computational Geometry Theory and Applications 2:55-80, 1992. (2007)

Olivier Devillers, Stefan Meiser, Monique Teillaud

Once upon a time was a Delaunay tree that wanted to get rid of some site p or murders in the Delaunay tree.

x (2007)

Olivier Devillers, Franco P. Preparata, Roberto Tamassia

This paper studies the problem of verifying the correctness of geometric structures. In particular, we design optimal checkers for convex polytopes in two and higher dimensions, and for various types...

The Union of Unit Balls Has Quadratic Complexity, Even If They All Contain the Origin (2007)

Herv Brnnimann And, Herv Br#nnimann, Olivier Devillers

We provide a lower bound construction showing that the union of unit balls in R 3 has quadratic complexity, even if they all contain the origin. This settles a conjecture of Sharir. 1 Introduction...

Chromatic Variants of the Erds-Szekeres Theorem on Points in Convex Position (2007)

Olivier Devillers, Ferran Hurtado, Carlos Seara, Thme Gnie Logiciel, Projets Prisme

apport de recherche

Removing degeneracies by perturbing the problem or perturbing the world (2007)

Pierre Alliez, Olivier Devillers, Jack Snoeyink

We describe two problem-specic approaches to remove geometric degeneracies that we call perturbing the problem and perturbing the world. Using the example of Delaunay triangulation, we show that...

de recherche Improved Incremental Randomized Delaunay Triangulation. (2007)

Olivier Devillers, Olivier Devillers, Thème Génie Logiciel, Projet Prisme

apport

The Space of Spheres, a Geometric Tool to Uni f y Duality Results onVoronoi Diagrams (2007)

Olivier Devillers, Stefan Meiser, Monique Teillaud, Route Deslucioles

L'Espace des Sph`eres, unouti l g'eom'etri queunifiantles r'esultats dedualit'esur l es diagrammes deVoronoi

x (2007)

Olivier Devillers, Vida Dujmovi C, Hazel Everett, Xavier Goaoc, Sylvain Lazard, Hyeon-suk Na, ...

A linear bound on the expected

Olivier Devillers, Olivier Devillers, Thme Gnie Logiciel, Projet Geometrica

apport de recherche

of Subdivisions (2007)

Olivier Devillers, Olivier Devillers, Franco P. Preparata, Franco P. Preparata, Roberto Tamassia, Roberto Tamassia, ...

apport de recherche

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

Hervé Brönnimann, Hervé Brönnimann, Olivier Devillers, Olivier Devillers, Thème Génie Logiciel, Projet Prisme, ...

The union of unit balls has quadratic complexity,

Olivier Devillers, Olivier Devillers, Projets Prisme

apport de recherche

Circular Separability ofPolygons (2007)

Mariette Yvinec, Jean-daniel Boissonnat, Jean-daniel Boissonnat, Jurek Czyzowicz, Jurek Czyzowicz, Olivier Devillers, ...

novembre 94

Theory and Applications. (2007)

Olivier Devillers, Stefan Meiser, Monique Teillaud

Triangulation de Delaunay pleinement dynamique en temps tooyen logarithmique par opalration

a;2 (2007)

Mark De Berg, Olivier Devillers, Katrin Dobrindt, Otfried Schwarzkopf

b;1

International Journal of Computational Geometry & Applications c fl World Scientic Publishing Company SCALABLE ALGORITHMS FOR BICHROMATIC LINE SEGMENT INTERSECTION PROBLEMS ON COARSE GRAINED MULTICOMPUTERS (2007)

Andreas Fabri, Olivier Devillers

We present output-sensitive scalable parallel algorithms for bichromatic line segment intersection problems for the coarse grained multicomputer model. Under the assumption that n p 2, where n is the...

Revised In Submission (2007)

Olivier Devillers, Jorge Urrutia, Mariette Yvinec, Communicated F. Preparata

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

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

i (2007)

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

Evaluating (2007)

Francis Avnaim, Jean-daniel Boissonnat, Olivier Devillers, Franco P. Preparata, Mariette Yvinec

signs of determinants using single-precision arithmetic

LEONBATTISTA DONATI x (2007)

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

Nordic Journal of Computing 6(1999), 422--428. FINDING AN ORDINARY CONIC AND AN ORDINARY (2007)

Mark De Berg, Olivier Devillers, Marc Van Kreveld, Otfried Schwarzkopf, Monique Teillaud

Abstract. Given a finite set of non-collinear points in the plane, there exists a line that passes through exactly two points. Such a line is called an ordinary line. An efficient algorithm for...

2 (2007)

Let P be a convex polygon in the plane with n vertices and let Q be a convex polygon with m vertices. We prove that the maximum number of combinatorially distinct placements of Q with respect to P...

c fl World Scientic Publishing Company OUTPUT SENSITIVE CONSTRUCTION OF THE DELAUNAY TRIANGULATION OF POINTS LYING IN TWO PLANES (2007)

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

c (2007)

Olivier Devillers, Franco P. Preparata, Roberto Tamassia

c

The Shuing Buoeer (2007)

Jacqueline Duquesne (2007)

The classical approach of computational geometry is the

Jean-daniel Boissonnat, Andr C#r#zo, Olivier Devillers

y--

The Shuing Buoeer (2007)

The classical approach of computational geometry is the search for algorithms having the best possible worst case complexity, unfortunately, these algorithms are often

The Shuing Buoeer (2007)

The classical approach of computational geometry is the search for algorithms having the best possible worst case complexity, unfortunately, these algorithms are often

Jean-daniel Boissonnat, Jean-daniel Boissonnat, Olivier Devillers, Olivier Devillers, Sylvain Lazard, Sylvain Lazard

apport de recherche

predicates on circle arcs (2007)

Apport De Recherche, Olivier Devillers Alex, Olivier Devillers, Ra Fronville, Bernard Mourrain, Monique Teillaud, ...

The purpose of this paper is to present a new method to design exact geometric predicates in algorithms dealing with curved objects such as circular arcs. We focus on the comparison of the abscissae...

de recherche Optimal Line Bipartitions of Point Sets (2007)

Apport De Recherche, Olivier Devillers, Olivier Devillers, Matthew J. Katz, Matthew J. Katz, Thème Génie Logiciel, ...

Let S be a set of n points in the plane. We study the following problem: Partition S by a line into two subsets S a and S b such that maxff#S a #;f#S b #g is minimal, where f is any monotone function...

de recherche Computational Geometry and Discrete Computations (2007)

Olivier Devillers, Olivier Devillers, Thème Génie Logiciel, Projet Prisme

apport

Robotique, (2007)

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

Scalable Algorithms for Bichromatic Line Segment Intersection Problems on Coarse (2007)

Unite De Recherche, Inria-sophia Antipolis, Et En Automatique, Route Des Lucioles, Olivier Devillers, Grained Multicomputers

Problemes d'intersection de segments de deux couleurs. Algorithmes paralleles aechelle adaptative pour machine a gros grain Olivier Devillers y Andreas Fabri y

ISSN (2007)

Alexandra Fronville, Olivier Devillers, Olivier Devillers, Ra Fronville, Bernard Mourrain, Bernard Mourrain, ...

apport de recherche

Olivier Devillers, Olivier Devillers, Franco P. Preparata, Franco P. Preparata, Thème Génie Logiciel, Projet Prisme, ...

apport

Olivier Devillers, Olivier Devillers, Sylvain Pion, Sylvain Pion, Projets Prisme

apport de recherche

de recherche Geometric Compression for Interactive Transmission (2007)

Olivier Devillers, Pierre-marie G, Thème Génie Logiciel, Projet Prisme

apport

Olivier Devillers, Olivier Devillers, Franco P. Preparata, Franco P. Preparata, Thème Génie Logiciel, Projet Prisme

apport de recherche Evaluating the cylindricity of a nominally cylindrical point set (draft)

de recherche Rounding Voronoi diagram (2007)

Olivier Devillers, Pierre-marie G, Thème Génie Logiciel, Projet Prisme

apport

Mathieu Desbrun (2007)

Pierre Alliez, Pierre Alliez, David Cohen-steiner, David Cohen-steiner, Olivier Devillers, Olivier Devillers, ...

apport de recherche

Pierre Alliez, Pierre Alliez, Olivier Devillers, Olivier Devillers, Jack Snoeyink, Jack Snoeyink, ...

Removing degeneracies by perturbing the

Olivier Devillers, Olivier Devillers, Thème Génie Logiciel, Projet Prisme, Unité Inria, Sophia Antipolis

apport

The Number of Cylindrical Shells (2007)

Unit Inria, Sophia Antipolis, Olivier Devillers, Olivier Devillers

apport de recherche

Symbolic Elimination for parallel manipulators (2007)

Olivier Devillers, Olivier Devillers, Ferran Hurtado, Ferran Hurtado, Carlos Seara, Carlos Seara, ...

apport de recherche

simple (2007)

Otfried Schwarzkopf, Mark De Berg, Mark De Berg, Olivier Devillers, Olivier Devillers, Katrin Dobrindt, ...

Computing a single cell in the union of two

Luc Tancredi, Luc Tancredi, Monique Teillaud, Monique Teillaud, Olivier Devillers, Olivier Devillers, ...

apport de recherche

Mark De Berg, Mark De Berg, Olivier Devillers, Olivier Devillers, Marc Van Kreveld, Marc Van Kreveld, ...

apport de recherche

Oin Ferran Hurtado, Pedro Ramos, Vera Sacristán, Olivier Devillers, Regina Estkowski Y, Pierre-marie G, ...

apport de recherche

Olivier Devillers, Olivier Devillers, Thme Gnie Logiciel, Projets Prisme

apport de recherche

Olivier Devillers, Olivier Devillers, Asish Mukhopadhyay, Asish Mukhopadhyay, Thème Génie Logiciel, Projet Prisme

apport de recherche Finding an ordinary conic and an ordinary hyperplane

ISSN (2007)

Apport De Recherche, Herv Brnnimann, Olivier Devillers, Unit Inria, Sophia Antipolis

We provide a lower bound construction showing that the union of unit balls in R has quadratic complexity, even if they all contain the origin. This settles a conjecture of Sharir.

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

Helly-type theorems for approximate covering (2007)

Demouth, Julien, Devillers, Olivier, Glisse, Marc, Goaoc, Xavier

Let F be a covering of a unit ball U in Rd by unit balls. We prove that for any epsilon >0, the smallest subset of F leaving at most a volume epsilon of U uncovered has size...

Helly-type theorems for approximate covering (2007)

Demouth, Julien, Devillers, Olivier, Glisse, Marc, Goaoc, Xavier

Let F be a covering of a unit ball U in Rd by unit balls. We prove that for any epsilon >0, the smallest subset of F leaving at most a volume epsilon of U uncovered has size...

Helly-type theorems for approximate covering (2007)

Demouth, Julien, Devillers, Olivier, Glisse, Marc, Goaoc, Xavier

Let F be a covering of a unit ball U in Rd by unit balls. We prove that for any epsilon >0, the smallest subset of F leaving at most a volume epsilon of U uncovered has size...

Helly-type theorems for approximate covering (2007)

Demouth, Julien, Devillers, Olivier, Glisse, Marc, Goaoc, Xavier

Let F be a covering of a unit ball U in Rd by unit balls. We prove that for any epsilon >0, the smallest subset of F leaving at most a volume epsilon of U uncovered has size...

Complexity of Delaunay Triangulation for Points on Lower-dimensional~Polyhedra (2007)

Amenta, Nina, Attali, Domiique, Devillers, Olivier

We show that the Delaunay triangulation of a set of points distributed nearly uniformly on a polyhedron (not necessarily convex) of dimension p in d-dimensional space is O(n^(d-1)/p))$. For all p...

Complexity of Delaunay Triangulation for Points on Lower-dimensional~Polyhedra (2007)

Amenta, Nina, Attali, Domiique, Devillers, Olivier

We show that the Delaunay triangulation of a set of points distributed nearly uniformly on a polyhedron (not necessarily convex) of dimension p in d-dimensional space is O(n^(d-1)/p))$. For all p...

Random sampling of a cylinder yields a not so nasty Delaunay triangulation (2007)

Random sampling of a cylinder yields a not so nasty Delaunay triangulation (2007)

We prove that the expected size of the 3D Delaunay triangulation of n points evenly distributed on a cylinder is Theta(n log n). This shows that the n sqrt(n) behavior of the cylinder-example of...

Lines tangent to four triangles in three-dimensional space (2007)

We prove that the expected size of the 3D Delaunay triangulation of n points evenly distributed on a cylinder is Theta(n log n). This shows that the n sqrt(n) behavior of the cylinder-example of...

Brönnimann, Hervé, Devillers, Olivier, Lazard, Sylvain, Sottile, Frank

We investigate the lines tangent to four triangles in $\mathbb{R}^3$. By a construction, there can be as many as 62 tangents. We show that there are at most 162 connected components of tangents, and...

Lines tangent to four triangles in three-dimensional space (2007)

Brönnimann, Hervé, Devillers, Olivier, Lazard, Sylvain, Sottile, Frank

We investigate the lines tangent to four triangles in $\mathbb{R}^3$. By a construction, there can be as many as 62 tangents. We show that there are at most 162 connected components of tangents, and...

Random sampling of a cylinder yields a not so nasty Delaunay triangulation (2007)

Random sampling of a cylinder yields a not so nasty Delaunay triangulation (2007)

We prove that the expected size of the 3D Delaunay triangulation of n points evenly distributed on a cylinder is Theta(n log n). This shows that the n sqrt(n) behavior of the cylinder-example of...

Helly-type theorems for approximate covering (2007)

We prove that the expected size of the 3D Delaunay triangulation of n points evenly distributed on a cylinder is Theta(n log n). This shows that the n sqrt(n) behavior of the cylinder-example of...

Demouth, Julien, Devillers, Olivier, Glisse, Marc, Goaoc, Xavier

Let F be a covering of a unit ball U in Rd by unit balls. We prove that for any epsilon >0, the smallest subset of F leaving at most a volume epsilon of U uncovered has size...

Helly-type theorems for approximate covering (2007)

Demouth, Julien, Devillers, Olivier, Glisse, Marc, Goaoc, Xavier

Let F be a covering of a unit ball U in Rd by unit balls. We prove that for any epsilon >0, the smallest subset of F leaving at most a volume epsilon of U uncovered has size...

Complexity of Delaunay Triangulation for Points on Lower-dimensional~Polyhedra (2007)

Amenta, Nina, Attali, Dominique, Devillers, Olivier

We show that the Delaunay triangulation of a set of points distributed nearly uniformly on a polyhedron (not necessarily convex) of dimension p in d-dimensional space is O(n^(d-1)/p))$. For all p...

Complexity of Delaunay Triangulation for Points on Lower-dimensional~Polyhedra (2007)

Amenta, Nina, Attali, Dominique, Devillers, Olivier

We show that the Delaunay triangulation of a set of points distributed nearly uniformly on a polyhedron (not necessarily convex) of dimension p in d-dimensional space is O(n^(d-1)/p))$. For all p...

On the Complexity of Umbra and Penumbra (2007)

Demouth, Julien, Devillers, Olivier, Everett, Hazel, Glisse, Marc, Lazard, Sylvain, Seidel, Raimund

Computing shadow boundaries is a difficult problem in the case of non-point light sources. A point is in the umbra if it does not see any part of any light source; it is in full light if it sees...

On the Complexity of Umbra and Penumbra (2007)

Demouth, Julien, Devillers, Olivier, Everett, Hazel, Glisse, Marc, Lazard, Sylvain, Seidel, Raimund

Computing shadow boundaries is a difficult problem in the case of non-point light sources. A point is in the umbra if it does not see any part of any light source; it is in full light if it sees...

Between umbra and penumbra (2007)

Demouth, Julien, Devillers, Olivier, Everett, Hazel, Glisse, Marc, Lazard, Sylvain, Seidel, Raimund

Computing shadow boundaries is a difficult problem in the case of non-point light sources. A point is in the umbra if it does not see any part of any light source; it is in full light if it sees...

Between umbra and penumbra (2007)

Demouth, Julien, Devillers, Olivier, Everett, Hazel, Glisse, Marc, Lazard, Sylvain, Seidel, Raimund

Computing shadow boundaries is a difficult problem in the case of non-point light sources. A point is in the umbra if it does not see any part of any light source; it is in full light if it sees...

Lines and free line segments Tangent to Arbitrary Three-dimensional Convex Polyhedra (2007)

Bronnimann, Hervé, Devillers, Olivier, Dujmovic, Vida, Everett, Hazel, Glisse, Marc, Goaoc, Xavier, ...

Motivated by visibility problems in three dimensions, we investigate the complexity and construction of the set of tangent lines in a scene of three-dimensional polyhedra. We prove that the set of...

Lines and free line segments Tangent to Arbitrary Three-dimensional Convex Polyhedra (2007)

Bronnimann, Hervé, Devillers, Olivier, Dujmovic, Vida, Everett, Hazel, Glisse, Marc, Goaoc, Xavier, ...

Motivated by visibility problems in three dimensions, we investigate the complexity and construction of the set of tangent lines in a scene of three-dimensional polyhedra. We prove that the set of...

Maintaining Visibility Information of Planar Point Sets with a Moving Viewpoint (2007)

Devillers, Olivier, Dujmovic, Vida, Everett, Hazel, Hornus, Samuel, Whitesides, Sue, Wismath, Steve

Given a set of n points in the plane, we consider the problem of computing the circular ordering of the points about a viewpoint q and efficiently maintaining this ordering information as q moves. In...

Maintaining Visibility Information of Planar Point Sets with a Moving Viewpoint (2007)

Devillers, Olivier, Dujmovic, Vida, Everett, Hazel, Hornus, Samuel, Whitesides, Sue, Wismath, Steve

Given a set of n points in the plane, we consider the problem of computing the circular ordering of the points about a viewpoint q and efficiently maintaining this ordering information as q moves. In...

Complexity of Delaunay triangulation for points on lower-dimensional polyhedra (2007)

Thème Sym, Nina Amenta, Nina Amenta, Dominique Attali, Dominique Attali, Olivier Devillers, ...

apport de recherche ISSN 0249-6399 ISRN INRIA/RR--5986--FR+ENG Complexity of Delaunay triangulation for points on lower-dimensional polyhedra

Inner and Outer Rounding of Boolean Operations on Lattice Polygonal Regions (2006)

Drawing K_n in Three Dimensions with One Bend per Edge (2006)

Robustness problems due to the substitution of the exact computation on real numbers by the rounded floating point arithmetic are often an obstacle to obtain practical implementation of geometric...

Devillers, Olivier, Everett, Hazel, Lazard, Sylvain, Pentcheva, Maria, Wismath, Stephen

We give a drawing of K_n in three dimensions in which vertices are placed at integer grid points and edges are drawn crossing-free with at most one bend per edge in a volume bounded by O(n^{2.5})....

Drawing K_n in Three Dimensions with One Bend per Edge (2006)

Devillers, Olivier, Everett, Hazel, Lazard, Sylvain, Pentcheva, Maria, Wismath, Stephen

We give a drawing of K_n in three dimensions in which vertices are placed at integer grid points and edges are drawn crossing-free with at most one bend per edge in a volume bounded by O(n^{2.5})....

Optimal succinct representation of planar maps (2006)

Castelli Aleardi, Luca, Devillers, Olivier, Schaeffer, Gilles

This paper addresses the problem of representing the connectivity information of geometric objects using as little memory as possible. As opposed to raw compression issues, the focus is here on...

Optimal succinct representation of planar maps (2006)

Castelli Aleardi, Luca, Devillers, Olivier, Schaeffer, Gilles

This paper addresses the problem of representing the connectivity information of geometric objects using as little memory as possible. As opposed to raw compression issues, the focus is here on...

Dynamic updates of succinct triangulations (2006)

Castelli Aleardi, Luca, Devillers, Olivier, Schaeffer, Gilles

In a recent article, we presented a succinct representation of triangulations that supports efficient navigation operations. Here this representation is improved to allow for efficient local updates...

Farthest Point Seeding for Placement of Streamlines (2006)

Mebarki, Abdelkrim, Alliez, Pierre, Devillers, Olivier

We propose a novel algorithm for placement of streamlines from two-dimensional steady vector or direction fields. Our method consists of placing one streamline at a time by numerical integration...

Compact representation of triangulations (2006)

Castelli Aleardi, Luca, Devillers, Olivier, Schaeffer, Gilles

We consider the problem of representing compact geometric data structures maintaining an efficient implementation of navigation operations. For the case of planar triangulations with $m$ faces, we...

Perturbations and Vertex Removal in Delaunay and Regular 3D Triangulations (2006)

Perturbations and Vertex Removal in Delaunay and Regular 3D Triangulations (2006)

Though Delaunay and regular triangulations are very well known geometric data structures, the problem of the robust removal of a vertex in a three-dimensional triangulation is actually a problem in...

2D Triangulation Representation Using Stable Catalogs (2006)

Though Delaunay and regular triangulations are very well known geometric data structures, the problem of the robust removal of a vertex in a three-dimensional triangulation is actually a problem in...

Devillers, Olivier, Mebarki, Abdelkrim, Castelli Aleardi, Luca

The problem of representing triangulations has been widely studied to obtain convenient encodings and space efficient data structures. In this paper we propose a new practical approach to reduce the...

2D Triangulation Representation Using Stable Catalogs (2006)

Devillers, Olivier, Mebarki, Abdelkrim, Castelli Aleardi, Luca

The problem of representing triangulations has been widely studied to obtain convenient encodings and space efficient data structures. In this paper we propose a new practical approach to reduce the...

Perturbations and Vertex Removal in Delaunay and Regular 3D Triangulations (2006)

Perturbations and Vertex Removal in Delaunay and Regular 3D Triangulations (2006)

Though Delaunay and regular triangulations are very well known geometric data structures, the problem of the robust removal of a vertex in a three-dimensional triangulation is actually a problem in...

Complexity of Delaunay triangulation for points on lower-dimensional~polyhedra (2006)

Though Delaunay and regular triangulations are very well known geometric data structures, the problem of the robust removal of a vertex in a three-dimensional triangulation is actually a problem in...

Amenta, Nina, Attali, Dominique, Devillers, Olivier

We show that the Delaunay triangulation of a set of points distributed nearly uniformly on a polyhedron (not necessarily convex) of dimension p in d-dimensional space is of order n to the power...

Complexity of Delaunay triangulation for points on lower-dimensional~polyhedra (2006)

Amenta, Nina, Attali, Domiique, Devillers, Olivier

We show that the Delaunay triangulation of a set of points distributed nearly uniformly on a polyhedron (not necessarily convex) of dimension p in d-dimensional space is of order n to the power...

Optimal Succinct Representations of Planar Maps (2006)

Castelli Aleardi, Luca, Devillers, Olivier, Schaeffer, Gilles

This paper addresses the problem of representing the connectivity information of geometric objects using as little memory as possible. As opposed to raw compression issues, the focus is here on...

Optimal Succinct Representations of Planar Maps (2006)

Castelli Aleardi, Luca, Devillers, Olivier, Schaeffer, Gilles

This paper addresses the problem of representing the connectivity information of geometric objects using as little memory as possible. As opposed to raw compression issues, the focus is here on...

Optimal succinct representation of planar maps (2006)

Castelli Aleardi, Luca, Devillers, Olivier, Schaeffer, Gilles

This paper addresses the problem of representing the connectivity information of geometric objects using as little memory as possible. As opposed to raw compression issues, the focus is here on...

Complexity of Delaunay triangulation for points on lower-dimensional~polyhedra (2006)

Amenta, Nina, Attali, Dominique, Devillers, Olivier

We show that the Delaunay triangulation of a set of points distributed nearly uniformly on a polyhedron (not necessarily convex) of dimension p in d-dimensional space is of order n to the power...

Optimal Succinct Representations of Planar Maps (2006)

Castelli Aleardi, Luca, Devillers, Olivier, Schaeffer, Gilles

This paper addresses the problem of representing the connectivity information of geometric objects using as little memory as possible. As opposed to raw compression issues, the focus is here on...

Perturbations and Vertex Removal in Delaunay and Regular 3D Triangulations (2006)

2D Triangulation Representation Using Stable Catalogs (2006)

Though Delaunay and regular triangulations are very well known geometric data structures, the problem of the robust removal of a vertex in a three-dimensional triangulation is actually a problem in...

Devillers, Olivier, Mebarki, Abdelkrim, Castelli Aleardi, Luca

The problem of representing triangulations has been widely studied to obtain convenient encodings and space efficient data structures. In this paper we propose a new practical approach to reduce the...

Dynamic updates of succinct triangulations (2006)

Castelli Aleardi, Luca, Devillers, Olivier, Schaeffer, Gilles

In a recent article, we presented a succinct representation of triangulations that supports efficient navigation operations. Here this representation is improved to allow for efficient local updates...

Farthest Point Seeding for Placement of Streamlines (2006)

Mebarki, Abdelkrim, Alliez, Pierre, Devillers, Olivier

We propose a novel algorithm for placement of streamlines from two-dimensional steady vector or direction fields. Our method consists of placing one streamline at a time by numerical integration...

Compact representation of triangulations (2006)

Castelli Aleardi, Luca, Devillers, Olivier, Schaeffer, Gilles

We consider the problem of representing compact geometric data structures maintaining an efficient implementation of navigation operations. For the case of planar triangulations with $m$ faces, we...

Drawing $K_n$ in Three Dimensions with One Bend per Edge (2006)

Devillers, Olivier, Everett, Hazel, Lazard, Sylvain, Pentcheva, Maria, Wismath, Steve

We give a drawing of $K_n$ in three dimensions in which vertices are placed at integer grid points and edges are drawn crossing-free with at most one bend per edge in a volume bounded by~$O(n^{2.5})$.

Drawing $K_n$ in Three Dimensions with One Bend per Edge (2006)

Devillers, Olivier, Everett, Hazel, Lazard, Sylvain, Pentcheva, Maria, Wismath, Steve

We give a drawing of $K_n$ in three dimensions in which vertices are placed at integer grid points and edges are drawn crossing-free with at most one bend per edge in a volume bounded by~$O(n^{2.5})$.

Drawing K_n in Three Dimensions with One Bend per Edge (2006)

Devillers, Olivier, Everett, Hazel, Lazard, Sylvain, Pentcheva, Maria, Wismath, Stephen

We give a drawing of K_n in three dimensions in which vertices are placed at integer grid points and edges are drawn crossing-free with at most one bend per edge in a volume bounded by O(n^{2.5})....

Lines and free line segments tangent to arbitrary three-dimensional convex polyhedra (2006)

Olivier Devillers, Vida Dujmović, Hazel Everett, Marc Glisse, Xavier Goaoc, Sylvain Lazard, ...

SUE WHITESIDES∗ ∗ Abstract. Motivated by visibility problems in three dimensions, we investigate the complexity and construction of the set of tangent lines in a scene of three-dimensional...

Lines and free line segments tangent to arbitrary three-dimensional convex polyhedra (2006)

Hervé Brönnimann, Olivier Devillers, Vida Dujmović, Hazel Everett, Xavier Goaoc, Sylvain Lazard, ...

Abstract. Motivated by visibility problems in three dimensions, we investigate the complexity and construction of the set of tangent lines in a scene of three-dimensional polyhedra. We prove that the...

Inner and Outer Rounding of Boolean Operations on Lattice Polygonal Regions (2006)

Lines tangent to four triangles in three-dimensional space (2005)

Robustness problems due to the substitution of the exact computation on real numbers by the rounded floating point arithmetic are often an obstacle to obtain practical implementation of geometric...

Brönnimann, Hervé, Devillers, Olivier, Lazard, Sylvain, Sottile, Frank

We investigate the lines tangent to four triangles in three-dimensional space. By a construction, there can be as many as 62 tangents. We show that there are at most 162 connected components of...

On the Number of Maximal Free Line Segments Tangent to Arbitrary Three-dimensional Convex Polyhedra (2005)

Brönnimann, Hervé, Devillers, Olivier, Dujmovic, Vida, Everett, Hazel, Glisse, Marc, Goaoc, Xavier, ...

We prove that the lines tangent to four possibly intersecting convex polyhedra in $^3$ with $n$ edges in total form $\Theta(n^2)$ connected components in the worst case. In the generic case, each...

Drawing Kn in Three Dimensions with One Bend per Edge (2005)

Devillers, Olivier, Everett, Hazel, Lazard, Sylvain, Pentcheva, Maria, Wismath, Stephen

We give a drawing of $K_n$ in three dimensions in which vertices are placed at integer grid points and edges are drawn crossing-free with at most one bend per edge in a volume bounded by $O(n^2.5)$.

Lines tangent to four triangles in three-dimensional space (2005)

Brönnimann, Hervé, Devillers, Olivier, Lazard, Sylvain, Sottile, Frank

We investigate the lines tangent to four triangles in three-dimensional space. By a construction, there can be as many as 62 tangents. We show that there are at most 162 connected components of...

On the Number of Maximal Free Line Segments Tangent to Arbitrary Three-dimensional Convex Polyhedra (2005)

Brönnimann, Hervé, Devillers, Olivier, Dujmovic, Vida, Everett, Hazel, Glisse, Marc, Goaoc, Xavier, ...

We prove that the lines tangent to four possibly intersecting convex polyhedra in $^3$ with $n$ edges in total form $\Theta(n^2)$ connected components in the worst case. In the generic case, each...

Drawing Kn in Three Dimensions with One Bend per Edge (2005)

Devillers, Olivier, Everett, Hazel, Lazard, Sylvain, Pentcheva, Maria, Wismath, Stephen

We give a drawing of $K_n$ in three dimensions in which vertices are placed at integer grid points and edges are drawn crossing-free with at most one bend per edge in a volume bounded by $O(n^2.5)$.

Maintaining Visibility Information of Planar Point Sets with a Moving Viewpoint (2005)

Devillers, Olivier, Dujmovic, Vida, Everett, Hazel, Hornus, Samuel, Whitesides, Sue, Wismath, Steve

Given a set of $n$ points in the plane, we consider the problem of computing the circular ordering of the points about a viewpoint $q$ and efficiently maintaining this ordering information as $q$...

On the Number of Maximal Free Line Segments Tangent to Arbitrary Three-dimensional Convex Polyhedra (2005)

Brönnimann, Hervé, Devillers, Olivier, Everett, Hazel, Glisse, Marc, Goaoc, Xavier, ...

We prove that the lines tangent to four possibly intersecting convex polyhedra in $ ^3$ with $n$ edges in total form $\Theta(n^2)$ connected components in the worst case. In the generic case, each...

Lines tangent to four triangles in three-dimensional space (2005)

Brönnimann, Hervé, Devillers, Olivier, Lazard, Sylvain, Sottile, Frank

We investigate the lines tangent to four triangles in three-dimensional space. By a construction, there can be as many as 62 tangents. We show that there are at most 162 connected components of...

Drawing $K_n$ in Three Dimensions with One Bend per Edge (2005)

Devillers, Olivier, Everett, Hazel, Lazard, Sylvain, Pentcheva, Maria, Wismath, Stephen

We give a drawing of $K_n$ in three dimensions in which vertices are placed at integer grid points and edges are drawn crossing-free with at most one bend per edge in a volume bounded by $O(n^2.5)$.

Castelli Aleardi, Luca, Devillers, Olivier, Schaeffer, Gilles

In a recent article, we presented a succinct representation of triangulations that supports efficient navigation operations. Here this representation is improved to allow for efficient local updates...

Farthest Point Seeding for Placement of Streamlines (2005)

Mebarki, Abdelkrim, Alliez, Pierre, Devillers, Olivier

We propose a novel algorithm for placement of streamlines from two-dimensional steady vector or direction fields. Our method consists of placing one streamline at a time by numerical integration...

Line tangents to four triangles in three-dimensional space (2005)

Brönnimann, Hervé, Devillers, Olivier, Lazard, Sylvain, Sottile, Frank

We investigate the lines tangent to four triangles in R^3. By a construction, there can be as many as 62 tangents. We show that there are at most 162 connected components of tangents, and at most 156...

Lines tangent to four triangles in three-dimensional space (2005)

Brönnimann, Hervé, Devillers, Olivier, Lazard, Sylvain, Sottile, Frank

We investigate the lines tangent to four triangles in $\mathbb{R}^3$. By a construction, there can be as many as 62 tangents. We show that there are at most 162 connected components of tangents, and...

Maintaining Visibility Information of Planar Point Sets with a Moving Viewpoint (2005)

Devillers, Olivier, Dujmovic, Vida, Everett, Hazel, Hornus, Samuel, Wismath, Steve, Whitesides, Sue

Given a set of n points in the plane, we consider the problem of computing the circular ordering of the points about a viewpoint q and efficiently maintaining this ordering information as q moves.

Drawing $K_n$ in Three Dimensions with One Bend per Edge (2005)

Devillers, Olivier, Everett, Hazel, Lazard, Sylvain, Pentcheva, Maria, Wismath, Stephen

We give a drawing of $K_n$ in 3D in which vertices are placed at integer grid points and edges are drawn crossing-free with at most one bend per edge in a volume bounded by $O(n^{2.5})$.

Castelli Aleardi, Luca, Devillers, Olivier, Schaeffer, Gilles

In a recent article, we presented a succinct representation of triangulations that supports efficient navigation operations. Here this representation is improved to allow for efficient local updates...

Inner and Outer Rounding of Boolean Operations on Lattice Polygonal Regions (2005)

Maintaining Visibility Information of Planar Point Sets with a Moving Viewpoint (2005)

Robustness problems due to the substitution of the exact computation on real numbers by the rounded floating point arithmetic are often an obstacle to obtain practical implementation of geometric...

Devillers, Olivier, Dujmovic, Vida, Everett, Hazel, Hornus, Samuel, Wismath, Steve, Whitesides, Sue

Given a set of n points in the plane, we consider the problem of computing the circular ordering of the points about a viewpoint q and efficiently maintaining this ordering information as q moves.

Drawing $K_n$ in Three Dimensions with One Bend per Edge (2005)

Devillers, Olivier, Everett, Hazel, Lazard, Sylvain, Pentcheva, Maria, Wismath, Stephen

We give a drawing of $K_n$ in 3D in which vertices are placed at integer grid points and edges are drawn crossing-free with at most one bend per edge in a volume bounded by $O(n^{2.5})$.

Castelli Aleardi, Luca, Devillers, Olivier, Schaeffer, Gilles

In a recent article, we presented a succinct representation of triangulations that supports efficient navigation operations. Here this representation is improved to allow for efficient local updates...

Inner and Outer Rounding of Boolean Operations on Lattice Polygonal Regions (2005)

Maintaining Visibility Information of Planar Point Sets with a Moving Viewpoint (2005)

Robustness problems due to the substitution of the exact computation on real numbers by the rounded floating point arithmetic are often an obstacle to obtain practical implementation of geometric...

Devillers, Olivier, Dujmovic, Vida, Everett, Hazel, Hornus, Samuel, Whitesides, Sue, Wismath, Steve

Given a set of $n$ points in the plane, we consider the problem of computing the circular ordering of the points about a viewpoint $q$ and efficiently maintaining this ordering information as $q$...

On the Number of Maximal Free Line Segments Tangent to Arbitrary Three-dimensional Convex Polyhedra (2005)

Brönnimann, Hervé, Devillers, Olivier, Dujmovic, Vida, Everett, Hazel, Glisse, Marc, Goaoc, Xavier, ...

We prove that the lines tangent to four possibly intersecting convex polyhedra in $ ^3$ with $n$ edges in total form $\Theta(n^2)$ connected components in the worst case. In the generic case, each...

Lines tangent to four triangles in three-dimensional space (2005)

Brönnimann, Hervé, Devillers, Olivier, Lazard, Sylvain, Sottile, Frank

We investigate the lines tangent to four triangles in three-dimensional space. By a construction, there can be as many as 62 tangents. We show that there are at most 162 connected components of...

Drawing $K_n$ in Three Dimensions with One Bend per Edge (2005)

Devillers, Olivier, Everett, Hazel, Lazard, Sylvain, Pentcheva, Maria, Wismath, Stephen

We give a drawing of $K_n$ in three dimensions in which vertices are placed at integer grid points and edges are drawn crossing-free with at most one bend per edge in a volume bounded by $O(n^2.5)$.

Castelli Aleardi, Luca, Devillers, Olivier, Schaeffer, Gilles

In a recent article, we presented a succinct representation of triangulations that supports efficient navigation operations. Here this representation is improved to allow for efficient local updates...

Succinct representation of triangulations with a boundary (2005)

Castelli Aleardi, Luca, Devillers, Olivier, Schaeffer, Gilles

We consider the problem of designing succinct geometric data structures while maintaining efficient navigation operations. A data structure is said succinct if the asymptotic amount of space it uses...

Castelli Aleardi, Luca, Devillers, Olivier, Schaeffer, Gilles

In a recent article, we presented a succinct representation of triangulations that supports efficient navigation operations. Here this representation is improved to allow for efficient local updates...

Succinct representation of triangulations with a boundary (2005)

Castelli Aleardi, Luca, Devillers, Olivier, Schaeffer, Gilles

We consider the problem of designing succinct geometric data structures while maintaining efficient navigation operations. A data structure is said succinct if the asymptotic amount of space it uses...

Succinct representation of triangulations with a boundary (2005)

Castelli Aleardi, Luca, Devillers, Olivier, Schaeffer, Gilles

We consider the problem of designing succinct geometric data structures while maintaining efficient navigation operations. A data structure is said succinct if the asymptotic amount of space it uses...

Maintaining Visibility Information of Planar Point Sets with a Moving Viewpoint (2005)

Devillers, Olivier, Dujmovic, Vida, Everett, Hazel, Hornus, Samuel, Whitesides, Sue, Wismath, Steve

Given a set of $n$ points in the plane, we consider the problem of computing the circular ordering of the points about a viewpoint $q$ and efficiently maintaining this ordering information as $q$...

On the Number of Maximal Free Line Segments Tangent to Arbitrary Three-dimensional Convex Polyhedra (2005)

Brönnimann, Hervé, Devillers, Olivier, Dujmovic, Vida, Everett, Hazel, Glisse, Marc, Goaoc, Xavier, ...

We prove that the lines tangent to four possibly intersecting convex polyhedra in $ ^3$ with $n$ edges in total form $\Theta(n^2)$ connected components in the worst case. In the generic case, each...

Lines tangent to four triangles in three-dimensional space (2005)

Brönnimann, Hervé, Devillers, Olivier, Lazard, Sylvain, Sottile, Frank

We investigate the lines tangent to four triangles in three-dimensional space. By a construction, there can be as many as 62 tangents. We show that there are at most 162 connected components of...

Drawing $K_n$ in Three Dimensions with One Bend per Edge (2005)

Devillers, Olivier, Everett, Hazel, Lazard, Sylvain, Pentcheva, Maria, Wismath, Stephen

We give a drawing of $K_n$ in three dimensions in which vertices are placed at integer grid points and edges are drawn crossing-free with at most one bend per edge in a volume bounded by $O(n^2.5)$.

Inner and Outer Rounding of Boolean Operations on Lattice Polygonal Regions (2005)

Robustness problems due to the substitution of the exact computation on real numbers by the rounded floating point arithmetic are often an obstacle to obtain practical implementation of geometric...

Castelli Aleardi, Luca, Devillers, Olivier, Schaeffer, Gilles

In a recent article, we presented a succinct representation of triangulations that supports efficient navigation operations. Here this representation is improved to allow for efficient local updates...

Maintaining Visibility Information of Planar Point Sets with a Moving Viewpoint (2005)

Devillers, Olivier, Dujmovic, Vida, Everett, Hazel, Hornus, Samuel, Wismath, Steve, Whitesides, Sue

Given a set of n points in the plane, we consider the problem of computing the circular ordering of the points about a viewpoint q and efficiently maintaining this ordering information as q moves.

Drawing $K_n$ in Three Dimensions with One Bend per Edge (2005)

Devillers, Olivier, Everett, Hazel, Lazard, Sylvain, Pentcheva, Maria, Wismath, Stephen

We give a drawing of $K_n$ in 3D in which vertices are placed at integer grid points and edges are drawn crossing-free with at most one bend per edge in a volume bounded by $O(n^{2.5})$.

Article Type Communicated by Submitted Revised (2005)

Olivier Devillers, Hazel Everett, Sylvain Lazard, Maria Pentcheva, Inria Lorraine, ...

We give a drawing of Kn in three dimensions in which vertices are placed at integer grid points and edges are drawn crossing-free with at most one bend per edge in a volume bounded by O(n 2.5).

Maintaining visibility information of planar point sets with a moving viewpoint (2005)

Olivier Devillers, Hazel Everett, Samuel Hornus, Sue Whitesides, Steve Wismathk

Abstract Given a set of n points in the plane, we consider theproblem of computing the circular ordering of the points about a viewpoint q and efficiently maintaining this or-dering information as q...

CAZALS F.: Accurate interactive specular reflections on curved objects (2005)

Pau Estalella, Ignacio Martin, George Drettakis, Dani Tost, Olivier Devillers, Frederic Cazals

We present a new method to compute interactive reflections on curved objects. The approach creates virtual reflected objects which are blended into the scene. We use a property of the reflection...

CAZALS F.: Accurate interactive specular reflections on curved objects (2005)

Pau Estalella, Ignacio Martin, George Drettakis, Dani Tost, Olivier Devillers, Frederic Cazals

We present a new method to compute interactive reflections on curved objects. The approach creates virtual reflected objects which are blended into the scene. We use a property of the reflection...

Article Type Communicated by Submitted Revised (2005)

Olivier Devillers, Hazel Everett, Sylvain Lazard, Maria Pentcheva, Inria Lorraine, ...

We give a drawing of Kn in three dimensions in which vertices are placed at integer grid points and edges are drawn crossing-free with at most one bend per edge in a volume bounded by O(n 2.5).

Compact representation of triangulations (2004)

Castelli Aleardi, Luca, Devillers, Olivier, Schaeffer, Gilles

We consider the problem of representing compact geometric data structures maintaining an efficient implementation of navigation operations. For the case of planar triangulations with $m$ faces, we...

Watermarking 3D triangle meshes for authentication and integrity (2004)

Cayre, François, Devillers, Olivier, Schmitt, Francis, Maître, Henri

Most watermarking schemes for 3D meshes arise from the CAD community. The analysis of their watermarking performances are generally not easily tractable. In this paper, we describe a framework for...

Canonical Triangulation of a Graph, with a Coding Application (2004)

Castelli Aleardi, Luca, Devillers, Olivier

For compression of 3D meshes, we propose an algorithm to encode the transformation of a polygonal mesh into a triangular mesh, getting a full coder by combination with a triangular coder. In this...

Watermarking 3D triangle meshes for authentication and integrity (2004)

Cayre, François, Devillers, Olivier, Schmitt, Francis, Maître, Henri

Most watermarking schemes for 3D meshes arise from the CAD community. The analysis of their watermarking performances are generally not easily tractable. In this paper, we describe a framework for...

Canonical Triangulation of a Graph, with a Coding Application (2004)

Castelli Aleardi, Luca, Devillers, Olivier

For compression of 3D meshes, we propose an algorithm to encode the transformation of a polygonal mesh into a triangular mesh, getting a full coder by combination with a triangular coder. In this...

Watermarking 3D triangle meshes for authentication and integrity (2004)

Cayre, François, Devillers, Olivier, Schmitt, Francis, Maître, Henri

Most watermarking schemes for 3D meshes arise from the CAD community. The analysis of their watermarking performances are generally not easily tractable. In this paper, we describe a framework for...

Canonical Triangulation of a Graph, with a Coding Application (2004)

Castelli Aleardi, Luca, Devillers, Olivier

For compression of 3D meshes, we propose an algorithm to encode the transformation of a polygonal mesh into a triangular mesh, getting a full coder by combination with a triangular coder. In this...

The Number of Lines Tangent to Arbitrary Convex Polyhedra in 3D (2004)

Brönnimann, Hervé, Devillers, Olivier, Dujmovic, Vida, Everett, Hazel, Glisse, Marc, Goaoc, Xavier, ...

We prove that the lines tangent to four possibly intersecting polytopes in $R3$ with $n$ edges in total form $\Theta(n^2)$ connected components. In the generic case, each connected component is a...

The Number of Lines Tangent to Arbitrary Convex Polyhedra in 3D (2004)

Brönnimann, Hervé, Devillers, Olivier, Dujmovic, Vida, Everett, Hazel, Glisse, Marc, Goaoc, Xavier, ...

We prove that the lines tangent to four possibly intersecting polytopes in $R3$ with $n$ edges in total form $\Theta(n^2)$ connected components. In the generic case, each connected component is a...

Inner and outer rounding of set operations on lattice polygonal regions (2004)

Olivier Devillers, Sophia Antipolis

Robustness problems due to the substitution of the exact computation on real numbers by the rounded floating point arithmetic are often an obstacle to obtain practical implementation of geometric...

Inner and Outer Rounding of Set Operations on Lattice Polygonal Regions (2003)

Robustness problems due to the substitution of the exact computation on real numbers by the rounded floating point arithmetic are often an obstacle to obtain practical implementation of geometric...

Alliez, Pierre, Cohen-Steiner, David, Devillers, Olivier, Lévy, Bruno, Desbrun, Mathieu

In this paper, we propose a novel polygonal remeshing technique that exploits a key aspect of surfaces: the intrinsic of natural or man-made geometry. In particular, we use curvature directions to...

Inner and Outer Rounding of Set Operations on Lattice Polygonal Regions (2003)

Robustness problems due to the substitution of the exact computation on real numbers by the rounded floating point arithmetic are often an obstacle to obtain practical implementation of geometric...

Alliez, Pierre, Cohen-Steiner, David, Devillers, Olivier, Lévy, Bruno, Desbrun, Mathieu

In this paper, we propose a novel polygonal remeshing technique that exploits a key aspect of surfaces: the intrinsic of natural or man-made geometry. In particular, we use curvature directions to...

The Number of Cylindrical Shells (2003)

The Number of Cylindrical Shells (2003)

Given a set P of n points in three dimensions, a cylindrical shell or zone cylinder is formed by two cylindrical cylinders with the same axis such that all points of P are between the two cylinders....

Inner and Outer Rounding of Set Operations on Lattice Polygonal Regions (2003)

Given a set P of n points in three dimensions, a cylindrical shell or zone cylinder is formed by two cylindrical cylinders with the same axis such that all points of P are between the two cylinders....

The Number of Cylindrical Shells (2003)

Robustness problems due to the substitution of the exact computation on real numbers by the rounded floating point arithmetic are often an obstacle to obtain practical implementation of geometric...

Given a set P of n points in three dimensions, a cylindrical shell or zone cylinder is formed by two cylindrical cylinders with the same axis such that all points of P are between the two cylinders....

Alliez, Pierre, Cohen-Steiner, David, Devillers, Olivier, Lévy, Bruno, Desbrun, Mathieu

In this paper, we propose a novel polygonal remeshing technique that exploits a key aspect of surfaces: the intrinsic of natural or man-made geometry. In particular, we use curvature directions to...

Perturbations and Vertex Removal in a 3D Delaunay Triangulation (2003)

Perturbations and Vertex Removal in a 3D Delaunay Triangulation (2003)

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

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

Alliez, Pierre, Cohen-Steiner, David, Devillers, Olivier, Lévy, Bruno, Desbrun, Mathieu

In this paper, we propose a novel polygonal remeshing technique that exploits a key aspect of surfaces: the intrinsic anisotropy of natural or man-made geometry. In particular, we use curvature...

Alliez, Pierre, Cohen-Steiner, David, Devillers, Olivier, Lévy, Bruno, Desbrun, Mathieu

In this paper, we propose a novel polygonal remeshing technique that exploits a key aspect of surfaces: the intrinsic anisotropy of natural or man-made geometry. In particular, we use curvature...

Efficient Exact Geometric Predicates for Delaunay Triangulations (2003)

Efficient Exact Geometric Predicates for Delaunay Triangulations (2003)

A time efficient implementation of the exact computation paradigm relies on arithmetic filters which are used to speed up the exact computation of easy instances of the geometric predicates....

The expected number of 3D visibility events is linear (2003)

A time efficient implementation of the exact computation paradigm relies on arithmetic filters which are used to speed up the exact computation of easy instances of the geometric predicates....

Th Emes Et, Vida Dujmovic, Sylvain Lazard, Olivier Devillers, Olivier Devillers, ...

apport de recherche

On circular cylinders by four or five points in space (2003)

Olivier Devillers, Bernard Mourrain, Franco P. Preparata, Philippe Trebuchet

Minimal Set of Constraints for 2D Constrained Delaunay Reconstruction (2003)

Olivier Devillers, Regina Estkowski, Ferran Hurtado, Pedro Ramos, Pierre-Marie Gandoin, Vera Sacristán

Given a triangulation T of n points in the plane, we are interested in the minimal set of edges in T such that T can be reconstructed from this set (and the vertices of T ) using constrained...

Minimal Set of Constraints for 2D Constrained Delaunay Reconstruction (2003)

Olivier Devillers, Regina Estkowski, Pierre-Marie Gandoin, Ferran Hurtado, Pedro Ramos, Vera Sacristán

Given a triangulation T of n points in the plane, we are interested in the minimal set of edges in T such that T can be reconstructed from this set (and the vertices of T ) using constrained Delaunay...

Chromatic Variants of the Erdös-Szekeres Theorem on Points in Convex Position (2003)

Olivier Devillers, Ferran Hurtado, Gyula Károlyi, Carlos Seara

Let S be a point set in the plane in general position, such that its elements are partitioned into k classes or colors. In this paper we study several variants on problems related to the...

Culling a Set of Points for Roundness or Cylindricity Evaluations (2003)

Culling a Set of Points for Roundness or Cylindricity Evaluations (2003)

Roundness and cylindricity evaluations are among the most important problems in computational metrology, and are based on sets of surface measurements (input data points). A recent approach to such...

Chromatic Variants of the Erdös-Szekeres Theorem on Points in Convex Position (2003)

Roundness and cylindricity evaluations are among the most important problems in computational metrology, and are based on sets of surface measurements (input data points). A recent approach to such...

Devillers, Olivier, Hurtado, Ferran, Károlyi, Gyula, Seara, Carlos

Let S be a point set in the plane in general position, such that its elements are partitioned into k classes or colors. In this paper we study several variants on problems related to the...

Chromatic Variants of the Erdös-Szekeres Theorem on Points in Convex Position (2003)

Devillers, Olivier, Hurtado, Ferran, Károlyi, Gyula, Seara, Carlos

Let S be a point set in the plane in general position, such that its elements are partitioned into k classes or colors. In this paper we study several variants on problems related to the...

Isotropic Surface Remeshing (2003)

Alliez, Pierre, Colin De Verdière, Éric, Devillers, Olivier, Isenburg, Martin

This paper proposes a new method for isotropic remeshing of tri- angulated surface meshes. Given a triangulated surface mesh to be resampled and a user-speciﬁed density function deﬁned over it,...

Isotropic Surface Remeshing (2003)

Alliez, Pierre, Colin De Verdière, Éric, Devillers, Olivier, Isenburg, Martin

This paper proposes a new method for isotropic remeshing of tri- angulated surface meshes. Given a triangulated surface mesh to be resampled and a user-speciﬁed density function deﬁned over it,...

Chromatic variants of the Erdös-Szekeres Theorem (2003)

Olivier Devillers, Ferran Hurtado, Carlos Seara

submitted to CGTA Abstract Let S be a point set in the plane in general position, such that its elements are partitioned into k classes or colors. In this paper we study several variants on problems...

The expected number of 3D visibility events is linear (2002)

Devillers, Olivier, Dujmovic, Vida, Everett, Hazel, Goaoc, Xavier, Lazard, Sylvain, Na, Hyeon-Suk, ...

In this paper, we show that, amongst n uniformly distributed unit balls in R^3, the expected number of maximal non-occluded line segments tangent to four balls is linear, considerably improving the...

Perturbations and Vertex Removal in a 3D Delaunay Triangulation (2002)

Isotropic Surface Remeshing (2002)

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

Alliez, Pierre, Colin De Verdière, Éric, Devillers, Olivier, Isenburg, Martin

This paper proposes a new method for isotropic remeshing of triangulated surface meshes. Given a triangulated surface mesh to be resampled and a user-specified density function defined over it, we...

Finite Precision Elementary Geometric Constructions (2002)

In this paper we propose a new approach for the robust computation of the nearest integer lattice points of some specific geometric constructions (intersection of two planar segments, circumcenter of...

Efficient Exact Geometric Predicates for Delaunay Triangulations (2002)

This paper presents a new method for computing whether or not two triangles in three dimensions intersect. The code is very efficient and requires minimum arithmetic precision. Indeed, all branching...

Chromatic Variants of the Erdös-Szekeres Theorem on Points in Convex Position (2002)

A time efficient implementation of the exact computation paradigm relies on arithmetic filters which are used to speed up the exact computation of easy instances of the geometric predicates....

Devillers, Olivier, Hurtado, Ferran, Seara, Carlos

Let S be a point set in the plane in general position, such that its elements are partitioned into k classes or colors. In this paper we study several variants on problems related to the...

The expected number of 3D visibility events is linear (2002)

Devillers, Olivier, Dujmovic, Vida, Everett, Hazel, Goaoc, Xavier, Lazard, Sylvain, Na, Hyeon-Suk, ...

In this paper, we show that, amongst n uniformly distributed unit balls in R^3, the expected number of maximal non-occluded line segments tangent to four balls is linear, considerably improving the...

Perturbations and Vertex Removal in a 3D Delaunay Triangulation (2002)

Isotropic Surface Remeshing (2002)

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

Alliez, Pierre, Colin De Verdière, Éric, Devillers, Olivier, Isenburg, Martin

This paper proposes a new method for isotropic remeshing of triangulated surface meshes. Given a triangulated surface mesh to be resampled and a user-specified density function defined over it, we...

Finite Precision Elementary Geometric Constructions (2002)

In this paper we propose a new approach for the robust computation of the nearest integer lattice points of some specific geometric constructions (intersection of two planar segments, circumcenter of...

Efficient Exact Geometric Predicates for Delaunay Triangulations (2002)

This paper presents a new method for computing whether or not two triangles in three dimensions intersect. The code is very efficient and requires minimum arithmetic precision. Indeed, all branching...

Chromatic Variants of the Erdös-Szekeres Theorem on Points in Convex Position (2002)

A time efficient implementation of the exact computation paradigm relies on arithmetic filters which are used to speed up the exact computation of easy instances of the geometric predicates....

Devillers, Olivier, Hurtado, Ferran, Seara, Carlos

Let S be a point set in the plane in general position, such that its elements are partitioned into k classes or colors. In this paper we study several variants on problems related to the...

Circular Cylinders by Four or Five Points in Space (2002)

Devillers, Olivier, Mourrain, Bernard, Preparata, Franco, Trebuchet, Philippe

We are interested in computing effectively cylinders through 5 points, and in other problems involved in metrology. In particular, we consider the cylinders through 4 points with a fix radius and...

Circular Cylinders by Four or Five Points in Space (2002)

Devillers, Olivier, Mourrain, Bernard, Preparata, Franco, Trebuchet, Philippe

We are interested in computing effectively cylinders through 5 points, and in other problems involved in metrology. In particular, we consider the cylinders through 4 points with a fix radius and...

Walking in a Triangulation (2002)

Devillers, Olivier, Pion, Sylvain, Teillaud, Monique

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

Walking in a Triangulation (2002)

Devillers, Olivier, Pion, Sylvain, Teillaud, Monique

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

Perturbations and Vertex Removal in a 3D Delaunay Triangulation (2002)

Isotropic Surface Remeshing (2002)

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

Alliez, Pierre, Colin De Verdière, Éric, Devillers, Olivier, Isenburg, Martin

This paper proposes a new method for isotropic remeshing of triangulated surface meshes. Given a triangulated surface mesh to be resampled and a user-specified density function defined over it, we...

Finite Precision Elementary Geometric Constructions (2002)

In this paper we propose a new approach for the robust computation of the nearest integer lattice points of some specific geometric constructions (intersection of two planar segments, circumcenter of...

Efficient Exact Geometric Predicates for Delaunay Triangulations (2002)

This paper presents a new method for computing whether or not two triangles in three dimensions intersect. The code is very efficient and requires minimum arithmetic precision. Indeed, all branching...

Chromatic Variants of the Erdös-Szekeres Theorem on Points in Convex Position (2002)

A time efficient implementation of the exact computation paradigm relies on arithmetic filters which are used to speed up the exact computation of easy instances of the geometric predicates....

Devillers, Olivier, Hurtado, Ferran, Seara, Carlos

Let S be a point set in the plane in general position, such that its elements are partitioned into k classes or colors. In this paper we study several variants on problems related to the...

Walking in a Triangulation (2002)

Devillers, Olivier, Pion, Sylvain, Teillaud, Monique

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

Circular Cylinders by Four or Five Points in Space (2002)

Devillers, Olivier, Mourrain, Bernard, Preparata, Franco, Trebuchet, Philippe

We are interested in computing effectively cylinders through 5 points, and in other problems involved in metrology. In particular, we consider the cylinders through 4 points with a fix radius and...

The expected number of 3D visibility events is linear (2002)

Devillers, Olivier, Dujmovic, Vida, Everett, Hazel, Goaoc, Xavier, Lazard, Sylvain, Na, Hyeon-Suk, ...

In this paper, we show that, amongst n uniformly distributed unit balls in R^3, the expected number of maximal non-occluded line segments tangent to four balls is linear, considerably improving the...

The Delaunay Hierarchy (2002)

Algebraic methods and arithmetic filtering for exact predicates on circle arcs (2002)

We propose a new data structure to compute the Delaunay triangulation of a set of points in the plane. It combines good worst case complexity, fast behavior on real data, small memory occupation and...

Devillers, Olivier, Fronville, Alexandra, Mourrain, Bernard, Teillaud, Monique

The purpose of this paper is to present a new method to design exact geometric predicates in algorithms dealing with curved objects such as circular arcs. We focus on the comparison of the abscissae...

The Delaunay Hierarchy (2002)

Algebraic methods and arithmetic filtering for exact predicates on circle arcs (2002)

We propose a new data structure to compute the Delaunay triangulation of a set of points in the plane. It combines good worst case complexity, fast behavior on real data, small memory occupation and...

Devillers, Olivier, Fronville, Alexandra, Mourrain, Bernard, Teillaud, Monique

The purpose of this paper is to present a new method to design exact geometric predicates in algorithms dealing with curved objects such as circular arcs. We focus on the comparison of the abscissae...

Progressive Lossless Compression of Arbitrary Simplicial Complexes (2002)

Gandoin, Pierre-Marie, Devillers, Olivier

Efficient algorithms for compressing geometric data have been widely developed in the recent years, but they are mainly designed for closed polyhedral surfaces which are ``manifol'' or ``nearly...

On Deletion in Delaunay Triangulations (2002)

Triangulations in CGAL (2002)

This paper presents how the space of spheres and shelling may be used to delete a point from a $d$-dimensional triangulation efficiently. In dimension two, if k is the degree of the deleted vertex,...

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.

Progressive Lossless Compression of Arbitrary Simplicial Complexes (2002)

Gandoin, Pierre-Marie, Devillers, Olivier

Efficient algorithms for compressing geometric data have been widely developed in the recent years, but they are mainly designed for closed polyhedral surfaces which are ``manifol'' or ``nearly...

On Deletion in Delaunay Triangulations (2002)

Triangulations in CGAL (2002)

This paper presents how the space of spheres and shelling may be used to delete a point from a $d$-dimensional triangulation efficiently. In dimension two, if k is the degree of the deleted vertex,...

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.

Perturbations and Vertex Removal in a 3D Delaunay Triangulation (2002)

Unit Inria, Sophia Antipolis, Olivier Devillers, Olivier Devillers, Monique Teillaud, Monique Teillaud, ...

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

Olivier Devilliers, Philippe Guigue, Olivier Devillers, Thème Génie Logiciel, Projets Prisme

This paper presents a new method for computing whether or not two triangles in three dimensions intersect. The code is very efficient and requires minimum arithmetic precision. Indeed, all branching...

Finite Precision Elementary Geometric Constructions (2002)

Olivier Devillers, Philippe Guigue, Olivier Devillers, Thème Génie Logiciel, Projets Prisme

In this paper we propose a new approach for the robust computation of the nearest integer lattice points of some specific geometric constructions (intersection of two planar segments, circumcenter of...

On the Number of Cylindrical Shells (2001)

On circular Cylinders by Four or Five Points in Space (2001)

Given a set $P$ of $n$ points in three dimensions, a cylindrical shell or zone cylinder is formed by two cylindrical cylinders with the same axis such that all points of $P$ are between the two...

Devillers, Olivier, Mourrain, Bernard, Preparata, Franco P., Trebuchet, Philippe

We are interested in computing effectively cylinders through 5 points, and in other problems involved in metrology. In particular, we consider the cylinders through 4 points with a fix radius and...

Compression interactive de maillages triangulaires arbitraires (2001)

Culling a Set of Points for Roundness or Cylindricity Evaluations (2001)

En quelques années, les maillages ont conquis une position prédominante parmi les différents modes de représentation informatique d'objets géométrique- s. Plus particulièrement, les maillages...

Splitting a Delaunay Triangulation in Linear Time (2001)

Roundness and cylindricity evaluations are among the most important problems in computational metrology, and are based on sets of surface measurements (input data points). A recent approach to such...

Chazelle, Bernard, Devillers, Olivier, Hurtado, Ferran, Mora, Mercè, Sacristán, Vera, Teillaud, Monique

Computing the Delaunay triangulation of $n$ points requires usually a minimum of $\Omega(n\log n)$ operations, but in some special cases where some additional knowledge is provided, faster algorithms...

Minimal Set of Constraints for 2D Constrained Delaunay Reconstruction (2001)

Devillers, Olivier, Estkowski, Regina, Gandoin, Pierre-Marie, Hurtado, Ferran, Ramos, Pedro, Sacristán, Vera

Given a triangulation $T$ of $n$ points in the plane, we are interested in the minimal set of edges in $T$ such that $T$ can be reconstructed from this set (and the vertices of $T$) using constrained...

Devillers, Olivier, Pion, Sylvain, Teillaud, Monique

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

On the Number of Cylindrical Shells (2001)

On circular Cylinders by Four or Five Points in Space (2001)

Given a set $P$ of $n$ points in three dimensions, a cylindrical shell or zone cylinder is formed by two cylindrical cylinders with the same axis such that all points of $P$ are between the two...

Devillers, Olivier, Mourrain, Bernard, Preparata, Franco P., Trebuchet, Philippe

We are interested in computing effectively cylinders through 5 points, and in other problems involved in metrology. In particular, we consider the cylinders through 4 points with a fix radius and...

Compression interactive de maillages triangulaires arbitraires (2001)

Culling a Set of Points for Roundness or Cylindricity Evaluations (2001)

En quelques années, les maillages ont conquis une position prédominante parmi les différents modes de représentation informatique d'objets géométrique- s. Plus particulièrement, les maillages...

Splitting a Delaunay Triangulation in Linear Time (2001)

Roundness and cylindricity evaluations are among the most important problems in computational metrology, and are based on sets of surface measurements (input data points). A recent approach to such...

Chazelle, Bernard, Devillers, Olivier, Hurtado, Ferran, Mora, Mercè, Sacristán, Vera, Teillaud, Monique

Computing the Delaunay triangulation of $n$ points requires usually a minimum of $\Omega(n\log n)$ operations, but in some special cases where some additional knowledge is provided, faster algorithms...

Minimal Set of Constraints for 2D Constrained Delaunay Reconstruction (2001)

Devillers, Olivier, Estkowski, Regina, Gandoin, Pierre-Marie, Hurtado, Ferran, Ramos, Pedro, Sacristán, Vera

Given a triangulation $T$ of $n$ points in the plane, we are interested in the minimal set of edges in $T$ such that $T$ can be reconstructed from this set (and the vertices of $T$) using constrained...

Devillers, Olivier, Pion, Sylvain, Teillaud, Monique

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

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

Splitting a Delaunay Triangulation in Linear Time (2001)

Chazelle, Bernard, Devillers, Olivier, Hurtado, Ferran, Mora, Merce, Sacristan, Vera, Teillaud, Monique

Computing the Delaunay triangulation of n points requires usually a minimum of Omega(n log n) operations, but in some special cases where some additional knowledge is provided, faster algorithms can...

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

Splitting a Delaunay Triangulation in Linear Time (2001)

Chazelle, Bernard, Devillers, Olivier, Hurtado, Ferran, Mora, Merce, Sacristan, Vera, Teillaud, Monique

Computing the Delaunay triangulation of n points requires usually a minimum of Omega(n log n) operations, but in some special cases where some additional knowledge is provided, faster algorithms can...

On the Number of Cylindrical Shells (2001)

On circular Cylinders by Four or Five Points in Space (2001)

Given a set $P$ of $n$ points in three dimensions, a cylindrical shell or zone cylinder is formed by two cylindrical cylinders with the same axis such that all points of $P$ are between the two...

Devillers, Olivier, Mourrain, Bernard, Preparata, Franco P., Trebuchet, Philippe

We are interested in computing effectively cylinders through 5 points, and in other problems involved in metrology. In particular, we consider the cylinders through 4 points with a fix radius and...

Compression interactive de maillages triangulaires arbitraires (2001)

Culling a Set of Points for Roundness or Cylindricity Evaluations (2001)

En quelques années, les maillages ont conquis une position prédominante parmi les différents modes de représentation informatique d'objets géométrique- s. Plus particulièrement, les maillages...

Splitting a Delaunay Triangulation in Linear Time (2001)

Roundness and cylindricity evaluations are among the most important problems in computational metrology, and are based on sets of surface measurements (input data points). A recent approach to such...

Chazelle, Bernard, Devillers, Olivier, Hurtado, Ferran, Mora, Mercè, Sacristán, Vera, Teillaud, Monique

Computing the Delaunay triangulation of $n$ points requires usually a minimum of $\Omega(n\log n)$ operations, but in some special cases where some additional knowledge is provided, faster algorithms...

Minimal Set of Constraints for 2D Constrained Delaunay Reconstruction (2001)

Devillers, Olivier, Estkowski, Regina, Gandoin, Pierre-Marie, Hurtado, Ferran, Ramos, Pedro, Sacristán, Vera

Given a triangulation $T$ of $n$ points in the plane, we are interested in the minimal set of edges in $T$ such that $T$ can be reconstructed from this set (and the vertices of $T$) using constrained...

Devillers, Olivier, Pion, Sylvain, Teillaud, Monique

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

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

Splitting a Delaunay Triangulation in Linear Time (2001)

Chazelle, Bernard, Devillers, Olivier, Hurtado, Ferran, Mora, Merce, Sacristan, Vera, Teillaud, Monique

Computing the Delaunay triangulation of n points requires usually a minimum of Omega(n log n) operations, but in some special cases where some additional knowledge is provided, faster algorithms can...

Walking in a Triangulation (2001)

Devillers, Olivier, Pion, Sylvain, Teillaud, Monique

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

Walking in a Triangulation (2001)

Devillers, Olivier, Pion, Sylvain, Teillaud, Monique

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

Olivier Devillers, Sylvain Pion, Monique Teillaud

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

Separating several point sets in the plane (2001)

Olivier Devillers, Olivier Devillers, Sylvain Pion, Sylvain Pion, Monique Teillaud, Monique Teillaud, ...

apport de recherche

Olivier Devillers, Ferran Hurtado, Carlos Seara

In this paper we study some problems on the separability of k disjoint point sets in the plane. On one hand, we give algorithms for nding minimum-cardinality separators by means of parallel lines or...

Splitting a Delaunay Triangulation in Linear Time (2001)

Bernard Chazelle, Bernard Chazelle, Olivier Devillers, Olivier Devillers, Ferran Hurtado, Ferran Hurtado, ...

Computing the Delaunay triangulation of n points requires usually a minimum of# n log n# operations, but in some special cases where some additional knowledge is provided, faster algorithms can be...

Culling a Set of Points For Roundness or Cylindricity Evaluations (2001)

Olivier Devillers, Olivier Devillers, Franco P. Preparata, Franco P. Preparata

Roundness and cylindricity evaluations are among the most important problems in computational metrology, and are based on sets of surface measurements (input data points). A recent approach to such...

On Circular Cylinders by Four or Five Points in Space (2001)

Unit Inria, Sophia Antipolis, Olivier Devillers, Olivier Devillers, Bernard Mourrain, Bernard Mourrain, ...

We are interested in computing eoeectively cylinders through 5 points, and in other problems involved in metrology. In particular, we consider the cylinders through 4 points with a x radius and with...

Splitting a Delaunay Triangulation in Linear Time (2001)

Vera Sacristn, Unit Inria, Sophia Antipolis, Bernard Chazelle, Bernard Chazelle, Olivier Devillers, ...

Computing the Delaunay triangulation of n points requires usually a minimum of n log n) operations, but in some special cases where some additional knowledge is provided, faster algorithms can be...

Walking in a Triangulation (2001)

Olivier Devillers, Sylvain Pion, Monique Teillaud, Thème Génie Logiciel, Projets Prisme, ...

Given a triangulation in the plane or a tetrahedralization in 3-space, weinvestigate the e#ciency of locating a pointbywalking in the structure with di#erent strategies. Key-words: Computational...

Minimal Set of Constraints for 2D Constrained Delaunay Reconstruction (2001)

Ferran Hurtado, Vera Sacristn, Unit Inria, Sophia Antipolis, Olivier Devillers, Olivier Devillers, ...

Given a triangulation T of n points in the plane, we are interested in the minimal set of edges in T such that T can be reconstructed from this set (and the vertices of T ) using constrained Delaunay...

On The Number Of Cylindrical Shells (2001)

Olivier Devillers, Olivier Devillers, Thème Génie Logiciel, Projets Prisme, Unité Inria, Sophia Antipolis

Given a set P of n points in three dimensions, a cylindrical shell or zone cylinder is formed bytwo cylindrical cylinders with the same axis such that all points of P are between the two cylinders....

The shuffling buffer (2001)

The shuffling buffer (2001)

The complexity of randomized incremental algorithms is analyzed with the assumption of a random order of the input. To guarantee this hypothesis, the n data have to be known in advance in order to be...

Le tampon mélangeur (2000)

The complexity of randomized incremental algorithms is analyzed with the assumption of a random order of the input. To guarantee this hypothesis, the n data have to be known in advance in order to be...

Geometric Compression for Interactive Transmission (2000)

Les méthodes de randomisation ont eu un grand succès en géométrie algorithmiqu- e car elles conduisent fréquemment à des algorithmes plus simples à programmer et parfois plus efficaces que...

Le tampon mélangeur (2000)

The compression of geometric structures is a relatively new field of data compression. Since about 1995, several articles have dealt with the coding of meshes, using for most of them the following...

Geometric Compression for Interactive Transmission (2000)

Les méthodes de randomisation ont eu un grand succès en géométrie algorithmique car elles conduisent fréquemment à des algorithmes plus simples à programmer et parfois plus efficaces que leurs...

Le tampon mélangeur (2000)

The compression of geometric structures is a relatively new field of data compression. Since about 1995, several articles have dealt with the coding of meshes, using for most of them the following...

Geometric Compression for Interactive Transmission (2000)

Les méthodes de randomisation ont eu un grand succès en géométrie algorithmique car elles conduisent fréquemment à des algorithmes plus simples à programmer et parfois plus efficaces que leurs...

Removing degeneracies by perturbing the problem or perturbing the world (2000)

The compression of geometric structures is a relatively new field of data compression. Since about 1995, several articles have dealt with the coding of meshes, using for most of them the following...

Removing degeneracies by perturbing the problem or perturbing the world (2000)

We describe two problem-specific approaches to remove geometric degeneracies that we call perturbing the problem and perturbing the world. Using as our primary examples 2-d and 3-d Delaunay...

Computing Largest Circles Separating Two Sets of Segments (2000)

We describe two problem-specific approaches to remove geometric degeneracies that we call perturbing the problem and perturbing the world. Using as our primary examples 2-d and 3-d Delaunay...

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

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

Geometric Compression for Interactive Transmission (2000)

Pierre-Marie Gandoin, Olivier Devillers, Olivier Devillers, Pierre-marie G

The compression of geometric structures is a relatively new eld of data compression. Since about 1995, several articles have dealt with the coding of meshes, using for most of them the following...

Evaluating the cylindricity of a nominally cylindrical point set (2000)

Evaluating the cylindricity of a nominally cylindrical point set (2000)

The minimum zone cylinder of a set of points in three dimensions is the cylindric crown defined by a pair of coaxial cylinders with minimal radial separation (width). In the context of tolerancing...

Algebraic Methods and Arithmetic Filtering for Exact Predicates on Circle Arcs (1999)

The minimum zone cylinder of a set of points in three dimensions is the cylindric crown defined by a pair of coaxial cylinders with minimal radial separation (width). In the context of tolerancing...

Devillers, Olivier, Fronville, Alexandra, Mourrain, Bernard, Teillaud, Monique

The purpose of this paper is to present a new method to design exact geometric predicates in algorithms dealing with curved objects such as circular arcs. We focus on the comparison of the abscissae...

Geometric compression for progressive transmission (1999)

Devillers, Olivier, Gandoin, Pierre-Maris

The compression of geometric structures is a relatively new field of data compression. Since about 1995, several articles have dealt with the coding of meshes, using for most of them the following...

Finding an ordinary conic and an ordinary hyperplane (1999)

Convex Tours of Bounded Curvature (1999)

Given a finite set of non-collinear points in the plane, there exists a line that passes through exactly two points. Such a line is called an ordinary line. An efficient algorithm for computing such...

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

The union of Unit Balls has Quadratic Complexity, even if They all Contain the Origin (1999)

Brönnimann, Hervé, Devillers, Olivier

We provide a lower bound construction showing that the union of unit balls in R3 has quadratic complexity, even if they all contain the origin. This settles a conjecture of Sharir.

Compression géométrique pour une transmission progressive (1999)

Further Results on Arithmetic Filters for Geometric Predicates (1999)

La compression de structures géométriques est un domaine relativement récent de la compression de données. Depuis 1995, plusieurs articles ont traité le problème du codage optimal de maillages,...

A Probabilistic Analysis of the Power of Arithmetic Filters (1999)

An efficient technique to solve precision problems consists in using exact computations. For geometric predicates, using systematically expensive exact computations can be avoided by the use of...

On Deletion in Delaunay Triangulation (1999)

The assumption of real-number arithmetic, which is at the basis of conventional geometric algorithms, has been seriously challenged in recent years, since digital computers do not exhibit such...

Improved Incremental Randomized Delaunay Triangulation (1999)

This paper presents how the space of spheres and shelling may be used to delete a point from a $d$-dimensional triangulation efficiently. In dimension two, if k is the degree of the deleted vertex,...

The union of unit balls has quadratic complexity, even if they all contain the origin (1999)

We propose a new data structure to compute the Delaunay triangulation of a set of points in the plane. It combines good worst case complexity, fast behavior on real data, and small memory occupation....

Bronnimann, Herve, Devillers, Olivier

We provide a lower bound construction showing that the union of unit balls in three-dimensional space has quadratic complexity, even if they all contain the origin. This settles a conjecture of...

Evaluating the Cylindricity of a Nominally Cylindrical Point Set (Draft) (1999)

Algebraic Methods and Arithmetic Filtering for Exact Predicates on Circle Arcs (1999)

The minimum zone cylinder of a set of points in three dimensions is the cylindric crown defined by a pair of coaxial cylinders with minimal radial separation (width). In the context of tolerancing...

Devillers, Olivier, Fronville, Alexandra, Mourrain, Bernard, Teillaud, Monique

The purpose of this paper is to present a new method to design exact geometric predicates in algorithms dealing with curved objects such as circular arcs. We focus on the comparison of the abscissae...

The union of Unit Balls has Quadratic Complexity, even if They all Contain the Origin (1999)

Brönnimann, Hervé, Devillers, Olivier

We provide a lower bound construction showing that the union of unit balls in R3 has quadratic complexity, even if they all contain the origin. This settles a conjecture of Sharir.

Compression géométrique pour une transmission progressive (1999)

Evaluating the Cylindricity of a Nominally Cylindrical Point Set (Draft) (1999)

La compression de structures géométriques est un domaine relativement récent de la compression de données. Depuis 1995, plusieurs articles ont traité le problème du codage optimal de maillages,...

Algebraic Methods and Arithmetic Filtering for Exact Predicates on Circle Arcs (1999)

The minimum zone cylinder of a set of points in three dimensions is the cylindric crown defined by a pair of coaxial cylinders with minimal radial separation (width). In the context of tolerancing...

Devillers, Olivier, Fronville, Alexandra, Mourrain, Bernard, Teillaud, Monique

The purpose of this paper is to present a new method to design exact geometric predicates in algorithms dealing with curved objects such as circular arcs. We focus on the comparison of the abscissae...

The union of Unit Balls has Quadratic Complexity, even if They all Contain the Origin (1999)

Brönnimann, Hervé, Devillers, Olivier

We provide a lower bound construction showing that the union of unit balls in R3 has quadratic complexity, even if they all contain the origin. This settles a conjecture of Sharir.

Compression géométrique pour une transmission progressive (1999)

Evaluating the Cylindricity of a Nominally Cylindrical Point Set (Draft) (1999)

La compression de structures géométriques est un domaine relativement récent de la compression de données. Depuis 1995, plusieurs articles ont traité le problème du codage optimal de maillages,...

Further Results on Arithmetic Filters for Geometric Predicates (1999)

The minimum zone cylinder of a set of points in three dimensions is the cylindric crown defined by a pair of coaxial cylinders with minimal radial separation (width). In the context of tolerancing...

Finding an ordinary conic and an ordinary hyperplane (1999)

An efficient technique to solve precision problems consists in using exact computations. For geometric predicates, using systematically expensive exact computations can be avoided by the use of...

Finding an ordinary conic and an ordinary hyperplane (1999)

Given a finite set of non-collinear points in the plane, there exists a line that passes through exactly two points. Such a line is called an ``ordinary line''. An efficient algorithm for computing...

Further Results on Arithmetic Filters for Geometric Predicates (1999)

Given a finite set of non-collinear points in the plane, there exists a line that passes through exactly two points. Such a line is called an ``ordinary line''. An efficient algorithm for computing...

Programming with CGAL: the example of triangulations (1999)

An efficient technique to solve precision problems consists in using exact computations. For geometric predicates, using systematically expensive exact computations can be avoided by the use of...

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.

Further results on arithmetic filters for geometric predicates (1999)

Olivier Devillers, Franco P. Preparata

An eOEcient technique to solve precision problems consists in using exact computations. For geometric predicates, using systematically expensive exact computations can be avoided by the use of lters....

Optimal line bipartitions of point sets (1999)

Olivier Devillers, Matthew J. Katz

Let S be a set of n points in the plane. We study the following problem: Partition S by a line into two subsets S a and S b such that maxff(S a); f(S b)g is minimal, where f is any monotone function...

On Deletion in Delaunay Triangulations (1999)

Evaluating The Cylindricity Of A Nominally Cylindrical Point Set (1999)

This paper presents how the space of spheres and shelling may be used to delete a point from a d-dimensional triangulation efficiently. In dimension two, if k is the degree of the deleted vertex, the...

Olivier Devillers, Olivier Devillers, Franco P. Preparata, Franco P. Preparata, Projet Prisme

The minimum zone cylinder of a set of points in three dimensions is the cylindric crown dened by a pair of coaxial cylinders with minimal radial separation (width). In the context of tolerancing...

On Deletion in Delaunay Triangulations (1999)

Convex Tours of Bounded Curvature. (1999)

This paper presents how the space of spheres and shelling may be used to delete a point from a -dimensional triangulation efficiently. In dimension two, if is the degree of the deleted vertex, the...

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

Randomization yields simple O(n log star n) algorithms for difficult Omega(n) problems (1998)

Finding an Ordinary Conic and an Ordinary Hyperplane (1998)

We use here the results on the influence graph by Boissonnat et al. to adapt them for particular cases where additional information is available. In some cases, it is possible to improve the expected...

Checking the Convexity of Polytopes and the Planarity of Subdivisions (1998)

Given a finite set of non-collinear points in the plane there exists a line that passes through exactly two points. Such a line is called an {\em ordinary line}. An efficient algorithm for computing...

Devillers, Olivier, Liotta, Giuseppe, Preparata, Franco P., Tamassia, Roberto

This paper considers the problem of verifying the correctness of geometric structures. In particular, we design simple optimal checkers for convex polytopes in two and higher dimensions, and for...

Further Results on Arithmetic Filters for Geometric Predicates (1998)

Computational Geometry and Discrete Computations (1998)

An efficient technique to solve precision problems consists in using exact computations. For geometric predicates, using systematically expensive exact computations can be avoided by the use of...

Computing the Maximum Overlap of Two Convex Polygons Under Translations (1998)

In this paper we describe some problems arising in practical implementation of algorithms from computational geometry. Going to robust algorithms needs to solve issues such as rounding errors and...

De Berg, Mark, Devillers, Olivier, Van Kreveld, Marc, Schwarzkopf, Otfried, Teillaud, Monique

Let P be a convex polygon in the plane with n vertices and let Q be a convex polygon with m vertices. We prove that the maximum number of combinatorially distinct placements of Q with respect to P...

Rounding Voronoi Diagram (1998)

Computational geometry classically assumes real-number arithmetic which does not exist in actual computers. A solution consists in using integer coordinates for data and exact arithmetic for...

Computing the maximum overlap of two convex polygons under translations (1998)

This paper present how space of spheres and shelling can be used to delete efficiently a point from d-dimensional triangulation. In 2-dimension, if k is the degree of the deleted vertex, the...

De Berg, Mark, Cheong, Otfried, Devillers, Olivier, Van Kreveld, Marc, Teillaud, Monique

Let P be a convex polygon in the plane with n vertices and let Q be a convex polygon with m vertices. We prove that the maximum number of combinatorially distinct placements of Q with respect to P...

Finding an Ordinary Conic and an Ordinary Hyperplane (1998)

Checking the Convexity of Polytopes and the Planarity of Subdivisions (1998)

Given a finite set of non-collinear points in the plane there exists a line that passes through exactly two points. Such a line is called an {\em ordinary line}. An efficient algorithm for computing...

Devillers, Olivier, Liotta, Giuseppe, Preparata, Franco P., Tamassia, Roberto

This paper considers the problem of verifying the correctness of geometric structures. In particular, we design simple optimal checkers for convex polytopes in two and higher dimensions, and for...

Further Results on Arithmetic Filters for Geometric Predicates (1998)

Computational Geometry and Discrete Computations (1998)

An efficient technique to solve precision problems consists in using exact computations. For geometric predicates, using systematically expensive exact computations can be avoided by the use of...

Rounding Voronoi Diagram (1998)

In this paper we describe some problems arising in practical implementation of algorithms from computational geometry. Going to robust algorithms needs to solve issues such as rounding errors and...

Computational geometry classically assumes real-number arithmetic which does not exist in actual computers. A solution consists in using integer coordinates for data and exact arithmetic for...

Finding an Ordinary Conic and an Ordinary Hyperplane (1998)

This paper present how space of spheres and shelling can be used to delete efficiently a point from d-dimensional triangulation. In 2-dimension, if k is the degree of the deleted vertex, the...

Checking the Convexity of Polytopes and the Planarity of Subdivisions (1998)

Given a finite set of non-collinear points in the plane there exists a line that passes through exactly two points. Such a line is called an {\em ordinary line}. An efficient algorithm for computing...

Devillers, Olivier, Liotta, Giuseppe, Preparata, Franco P., Tamassia, Roberto

This paper considers the problem of verifying the correctness of geometric structures. In particular, we design simple optimal checkers for convex polytopes in two and higher dimensions, and for...

Further Results on Arithmetic Filters for Geometric Predicates (1998)

Computational Geometry and Discrete Computations (1998)

An efficient technique to solve precision problems consists in using exact computations. For geometric predicates, using systematically expensive exact computations can be avoided by the use of...

Rounding Voronoi Diagram (1998)

In this paper we describe some problems arising in practical implementation of algorithms from computational geometry. Going to robust algorithms needs to solve issues such as rounding errors and...

Computational geometry classically assumes real-number arithmetic which does not exist in actual computers. A solution consists in using integer coordinates for data and exact arithmetic for...

Computing the maximum overlap of two convex polygons under translations (1998)

This paper present how space of spheres and shelling can be used to delete efficiently a point from d-dimensional triangulation. In 2-dimension, if k is the degree of the deleted vertex, the...

M. De Berg, O. Devillers, M. Van Kreveld, O. Schwarzkopf, Mark Berg, Olivier Devillers, ...

Let P be a convex polygon in the plane with n vertices and let Q be a convex polygon with m vertices. We prove that the maximum number of combinatorially distinct place-ments of Q with respect to P...

Improved incremental randomized Delaunay triangulation (1998)

A Probabilistic Analysis of the Power of Arithmetic Filters (1998)

The computation of the Delaunay triangulation of a set of n points in the plane is one of the classical problems in computational

Olivier Devillers, Olivier Devillers, Franco P. Preparata, Franco P. Preparata, Projet Prisme

The assumption of real-number arithmetic, which is at the basis of conventional geometric algorithms, has been seriously challenged in recent years, since digital computers do not exhibit such...

Computational Geometry and Discrete Computations (1998)

Olivier Devillers, Olivier Devillers

In this paper we describe some problems arising in practical implementation of algorithms from computational geometry. Going to robust algorithms needs to solve issues such as rounding errors and...

A Probabilistic Analysis of the Power of Arithmetic Filters (1998)

Franco P. Preparata, Olivier Devillers, Olivier Devillers, Franco P. Preparata

The assumption of real-number arithmetic, which is at the basis of conventional geometric algorithms, has been seriously challenged in recent years, since digital computers do not exhibit such...

Further Results on Arithmetic Filters for Geometric Predicates (1998)

Olivier Devillers, Olivier Devillers, Franco P. Preparata, Franco P. Preparata, Adresses O. Devillers

An eOEcient technique to solve precision problems consists in using exact computations. For geometric predicates, using systematically expensive exact computations can be avoided by the use of lters....

Rounding Voronoi diagram (1998)

Pierre-Marie Gandoin, Olivier Devillers, Olivier Devillers, Pierre-marie G

Computational geometry classically assumes real-number arithmetic which does not exist in actual computers. A solution consists in using integer coordinates for data and exact arithmetic for...

Olivier Devillers, Olivier Devillers

This paper present how space of spheres and shelling can be used to delete eOEciently a point from d-dimensional triangulation. In 2-dimension, if k is the degree of the deleted vertex, the...

Computing a Single Cell in the Overlay of two Simple Polygons (1998)

Mark De Berg, Olivier Devillers, Katrin Dobrindt, Otfried Schwarzkopf

Introduction The arrangement of n line segments in the plane can be computed using a randomized incremental algorithm in expected time O(n log n + A), where A is the number of intersection points of...

Finding an Ordinary Conic and an Ordinary Hyperplane (1998)

Olivier Devillers, Olivier Devillers, Asish Mukhopadhyay, Asish Mukhopadhyay

Given a nite set of non-collinear points in the plane there exists a line that passes through exactly two points. Such a line is called an ordinary line. An eOEcient algorithm for computing such a...

Improved Incremental Randomized Delaunay Triangulation (1998)

Checking the convexity of polytopes and the planarity of subdivisions. (1998)

this paper (minimal size for MSZ= ), # the mixed method suggested in Section 4.5 (default parameters above)

Devillers, Olivier, Liotta, Giuseppe, Preparata, Franco, Tamassia, Roberto

This paper considers the problem of verifying the correctness of geometric structures. In particular, we design simple optimal checkers for convex polytopes in two and higher dimensions, and for...

Computing the Maximum Overlap of Two Convex Polygons Under Translations. (1998)

Berg, Mark De, Devillers, Olivier, Kreveld, Marc Van, Schwarzkopf, Otfried, Teillaud, Monique

Let P be a convex polygon in the plane with n vertices and let Q be a convex polygon with m vertices. We prove that the maximum number of combinatorially distinct placements of Q with respect to P...

Checking the convexity of polytopes and the planarity of subdivisions. (1998)

Devillers, Olivier, Liotta, Giuseppe, Preparata, Franco, Tamassia, Roberto

This paper considers the problem of verifying the correctness of geometric structures. In particular, we design simple optimal checkers for convex polytopes in two and higher dimensions, and for...

Computing the Maximum Overlap of Two Convex Polygons Under Translations. (1998)

Berg, Mark De, Devillers, Olivier, Kreveld, Marc Van, Schwarzkopf, Otfried, Teillaud, Monique

Let P be a convex polygon in the plane with n vertices and let Q be a convex polygon with m vertices. We prove that the maximum number of combinatorially distinct placements of Q with respect to P...

Removing Degeneracies by Perturbing the Problem or the World (1997)

Improved Incremental Randomized Delaunay Triangulation. (1997)

We describe two problem-specific approaches to remove geometric degeneracies that we call {\it perturbing the problem} and {\it perturbing the world}. Using as our primary examples 2-d and 3-d...

Computing a Single Cell in the Overlay of two Simple Polygons (1997)

We propose a new data structure to compute the Delaunay triangulation of a set of points in the plane. It combines good worst case complexity, fast behavior on real data, and small memory occupation....

De Berg, Mark, Devillers, Olivier, Dobrindt, Katrin, Schwarzkopf, Otfried

This note combines the lazy randomized incremental construction scheme with the technique of “connectivity acceleration” to obtain an O(n(log* n)2) time randomized algorithm to compute a single...

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

A Probabilistic Analysis of the Power of Arithmetic Filters. (1997)

Removing Degeneracies by Perturbing the Problem or the World (1997)

The assumption of real-number arithmetic, which is at the basis of conventional geometric algorithms, has been seriously challenged in recent years, since digital computers do not exhibit such...

Improved Incremental Randomized Delaunay Triangulation. (1997)

We describe two problem-specific approaches to remove geometric degeneracies that we call {\it perturbing the problem} and {\it perturbing the world}. Using as our primary examples 2-d and 3-d...

Motion Planning of Legged Robots (1997)

We propose a new data structure to compute the Delaunay triangulation of a set of points in the plane. It combines good worst case complexity, fast behavior on real data, and small memory occupation....

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

Removing Degeneracies by Perturbing the Problem or the World (1997)

Improved Incremental Randomized Delaunay Triangulation. (1997)

We describe two problem-specific approaches to remove geometric degeneracies that we call {\it perturbing the problem} and {\it perturbing the world}. Using as our primary examples 2-d and 3-d...

Motion Planning of Legged Robots (1997)

We propose a new data structure to compute the Delaunay triangulation of a set of points in the plane. It combines good worst case complexity, fast behavior on real data, and small memory occupation....

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

A Probabilistic Analysis of the Power of Arithmetic Filters (1997)

Olivier Devillers, Franco P. Preparata

The assumption of real-number arithmetic, which is at the basis of conventional geometric algorithms, has been seriously challenged in recent years, since digital computers do not exhibit such...

Checking the Convexity of Polytopes and the Planarity of Subdivisions (1997)

Franco Preparata, Olivier Devillers, Olivier Devillers, Franco P. Preparata, Roberto Tamassia, ...

This paper considers the problem of verifying the correctness of geometric structures. In particular, we design optimal checkers for convex polytopes in two and higher dimensions, and for various...

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

Improved Incremental Randomized Delaunay Triangulation (1997)

Olivier Devillers, Olivier Devillers

: We propose a new data structure to compute the Delaunay triangulation of a set of points in the plane. It combines good worst case complexity, fast behavior on real data, and small memory...

Optimal Line Bipartitions of Point Sets (1997)

Olivier Devillers, Matthew J. Katz

Let S be a set of n points in the plane. We study the following problem: Partition S by a line into two subsets Sa and S b such that maxff(Sa ); f(S b )g is minimal, where f is any monotone function...

Computing a single cell in the union of two simple polygons (1997)

Berg, Mark De, Devillers, Olivier, Dobrindt, Katrin, Schwarzkopf, Otfried

This note combines the lazy randomized incremental construction scheme with the technique of ``connectivity acceleration'' to obtain an O( (n log*n)^2) time randomized algorithm to compute a single...

Computing a single cell in the union of two simple polygons (1997)

Berg, Mark De, Devillers, Olivier, Dobrindt, Katrin, Schwarzkopf, Otfried

This note combines the lazy randomized incremental construction scheme with the technique of ``connectivity acceleration'' to obtain an O( (n log*n)^2) time randomized algorithm to compute a single...

A Probabilistic Analysis of the Power of Arithmetic Filters (1996)

Optimal Line Bipartitions of Point Sets (1996)

The assumption of real-number arithmetic, which is at the basis of conventional geometric algorithms, has been seriously challenged in recent years, since digital computers do not exhibit such...

Devillers, Olivier, Katz, Matthew J.

Let $S$ be a set of $n$ points in the plane. We study the following problem: Partition $S$ by a line into two subsets $S_a$ and $S_b$ such that $max{f(S_a), f(S_b)}$ is minimal, where $f$ is any...

Computing the Maximum Overlap of Two Convex Polygons Under Translations (1996)

Berg, Mark De, Devillers, Olivier, Kreveld, Marc Van, Schwarzkopf, Otfried, Teillaud, Monique

Let $P$ be a convex polygon in the plane with $n$ vertices and let $Q$ be a convex polygon with $m$ vertices. We prove that the maximum number of combinatorially distinct placements of $Q$ with...

Symbolic Elimination for Parallel Manipulators (1996)

Tancredi, Luc, Teillaud, Monique, Devillers, Olivier

The forward kinematics problem of parallel robot consists in computing the position of a solid moving in the three-dimensional space with six points on it constrained to lie respectively on six given...

A Probabilistic Analysis of the Power of Arithmetic Filters (1996)

Optimal Line Bipartitions of Point Sets (1996)

The assumption of real-number arithmetic, which is at the basis of conventional geometric algorithms, has been seriously challenged in recent years, since digital computers do not exhibit such...

Devillers, Olivier, Katz, Matthew J.

Let $S$ be a set of $n$ points in the plane. We study the following problem: Partition $S$ by a line into two subsets $S_a$ and $S_b$ such that $max{f(S_a), f(S_b)}$ is minimal, where $f$ is any...

Computing the Maximum Overlap of Two Convex Polygons Under Translations (1996)

Berg, Mark De, Devillers, Olivier, Kreveld, Marc Van, Schwarzkopf, Otfried, Teillaud, Monique

Let $P$ be a convex polygon in the plane with $n$ vertices and let $Q$ be a convex polygon with $m$ vertices. We prove that the maximum number of combinatorially distinct placements of $Q$ with...

Symbolic Elimination for Parallel Manipulators (1996)

Tancredi, Luc, Teillaud, Monique, Devillers, Olivier

The forward kinematics problem of parallel robot consists in computing the position of a solid moving in the three-dimensional space with six points on it constrained to lie respectively on six given...

A probabilistic analysis of the power of arithmetic filters (1996)

A probabilistic analysis of the power of arithmetic filters (1996)

The assumption of real-number arithmetic, which is at the basis of conventional geometric algorithms, has been seriously challenged in recent years, since digital computers do not exhibit such...

A Probabilistic Analysis of the Power of Arithmetic Filters (1996)

The assumption of real-number arithmetic, which is at the basis of conventional geometric algorithms, has been seriously challenged in recent years, since digital computers do not exhibit such...

Optimal Line Bipartitions of Point Sets (1996)

The assumption of real-number arithmetic, which is at the basis of conventional geometric algorithms, has been seriously challenged in recent years, since digital computers do not exhibit such...

Devillers, Olivier, Katz, Matthew J.

Let $S$ be a set of $n$ points in the plane. We study the following problem: Partition $S$ by a line into two subsets $S_a$ and $S_b$ such that $max{f(S_a), f(S_b)}$ is minimal, where $f$ is any...

Computing the Maximum Overlap of Two Convex Polygons Under Translations (1996)

Berg, Mark De, Devillers, Olivier, Kreveld, Marc Van, Schwarzkopf, Otfried, Teillaud, Monique

Let $P$ be a convex polygon in the plane with $n$ vertices and let $Q$ be a convex polygon with $m$ vertices. We prove that the maximum number of combinatorially distinct placements of $Q$ with...

Symbolic Elimination for Parallel Manipulators (1996)

Tancredi, Luc, Teillaud, Monique, Devillers, Olivier

The forward kinematics problem of parallel robot consists in computing the position of a solid moving in the three-dimensional space with six points on it constrained to lie respectively on six given...

A probabilistic analysis of the power of arithmetic filters (1996)

An Introduction to Randomization in Computational Geometry. (1996)

The assumption of real-number arithmetic, which is at the basis of conventional geometric algorithms, has been seriously challenged in recent years, since digital computers do not exhibit such...

An Introduction to Randomization in Computational Geometry. (1996)

This paper is not a complete survey on randomized algorithms in computational geometry, but an introduction to this subject providing intuitions and references. In a first time, some basic ideas are...

Computational geometry and discrete computations (1996)

This paper is not a complete survey on randomized algorithms in computational geometry, but an introduction to this subject providing intuitions and references. In a first time, some basic ideas are...

Computational geometry and discrete computations (1996)

In this talk we describe some problems arising in practical implementation of algorithms from computational geometry. Going to robust algorithms needs to solve issues such as rounding errors and...

Computational geometry and discrete computations (1996)

In this talk we describe some problems arising in practical implementation of algorithms from computational geometry. Going to robust algorithms needs to solve issues such as rounding errors and...

Symbolic Elimination for Parallel Manipulators (1996)

Abstract. In this talk we describe some problems arising in practical implementation of algorithms from computational geometry. Going to robust algorithms needs to solve issues such as rounding...

Luc Tancredi, Luc Tancredi, Monique Teillaud, Monique Teillaud, Olivier Devillers, Olivier Devillers, ...

The forward kinematics problem of parallel robot consists in computing the position of a solid moving in the three-dimensional space with six points on it constrained to lie respectively on six given...

Computing the Maximum Overlap of Two Convex Polygons Under Translations (1996)

Mark De Berg, Mark De Berg, Olivier Devillers, Olivier Devillers, Marc Van Kreveld, Marc Van Kreveld, ...

Let P be a convex polygon in the plane with n vertices and let Q be a convex polygon with m vertices. We prove that the maximum number of combinatorially distinct placements of Q with respect to P...

Computing the Maximum Overlap of Two Convex Polygons Under Translations (1996)

Mark De Berg, Otfried Cheong, Olivier Devillers, Marc Van Kreveld, Monique Teillaud

Let P be a convex polygon in the plane with n vertices and let Q be a convex polygon with m vertices. We prove that the maximum number of combinatorially distinct placements of Q with respect to P...

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

Computing the Maximum Overlap of Two Convex Polygons Under Translations (1996)

Mark De, Mark De Berg, Otfried Cheong, Olivier Devillers, Marc Van Kreveld, Monique Teillaud

Let P be a convex polygon in the plane with n vertices and let Q be a convex polygon with m vertices. We prove that the maximum number of combinatorially distinct placements of Q with respect to P...

A Probabilistic Analysis of the Power of Arithmetic Filters (1996)

Olivier Devillers, Olivier Devillers, Franco P. Preparata, Franco P. Preparata, Thème Génie Logiciel, Projet Prisme

The assumption of real-number arithmetic, which is at the basis of conventional geometric algorithms, has been seriously challenged in recentyears, since digital computers do not exhibit such...

Queries on Voronoi Diagrams of Moving Points (1996)

Devillers, Olivier, Golin, Mordecai, Kedem, Klara, Schirra, Stefan

Suppose we are given n moving postmen described by their motion equations pi(t) = si + vi t, i=1, ... , n, where si belongs to R2 is the position of the i'th postman at time t=0, and vi in R2 is his...

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

Queries on Voronoi Diagrams of Moving Points (1996)

Devillers, Olivier, Golin, Mordecai, Kedem, Klara, Schirra, Stefan

Suppose we are given n moving postmen described by their motion equations pi(t) = si + vi t, i=1, ... , n, where si belongs to R2 is the position of the i'th postman at time t=0, and vi in R2 is his...

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

Computing a Single Cell in the Union of two Simple Polygons (1995)

De Berg, Mark, Devillers, Olivier, Dobrindt, Katrin, Schwarzkopf, Otfried

This note presents a non trivial combination of two techniques previously used with randomized incremental algorithms: the lazy cleaning scheme \cite{bds-lric-94} to maintain structures with `non...

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

Computing a Single Cell in the Union of two Simple Polygons (1995)

De Berg, Mark, Devillers, Olivier, Dobrindt, Katrin, Schwarzkopf, Otfried

This note presents a non trivial combination of two techniques previously used with randomized incremental algorithms: the lazy cleaning scheme \cite{bds-lric-94} to maintain structures with `non...

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

Computing a Single Cell in the Union of two Simple Polygons (1995)

De Berg, Mark, Devillers, Olivier, Dobrindt, Katrin, Schwarzkopf, Otfried

This note presents a non trivial combination of two techniques previously used with randomized incremental algorithms: the lazy cleaning scheme \cite{bds-lric-94} to maintain structures with `non...

A locally optimal triangulation of the hyperbolic paraboloid (1995)

Computing Largest Circles Separating Two Sets of Segments (1995)

and corresponding data values for a specic non-convex surface, the unit hyperbolic paraboloid, we consider the problem of nding a locally optimal triangulation of S for the linear approximation of...

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

Computing a Single Cell in the Union of Two Simple Polygons (1995)

Otfried Schwarzkopf, Mark De Berg, Mark De Berg, Olivier Devillers, Olivier Devillers, Katrin Dobrindt, ...

This note presents a non trivial combination of two techniques previously used with randomized incremental algorithms: the lazy cleaning scheme [dBDS94] to maintain structures with `non local'...

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

Incremental Algorithms for Finding the Convex Hulls of Circles and the Lower Envelopes of Parabolas (1995)

A Locally Optimal Triangulation of the Hyperbolic Paraboloid (1995)

The existing O(n log n) algorithms for finding the convex hulls of circles and the lower envelope of parabolas follow the divide-and-conquer paradigm. The difficulty with developing incremental...

Desnogues, Pascal, Devillers, Olivier

Given a set S of data points in R2 and corresponding data val ues for a specific non-convex surface, the unit hyperbolic paraboloid, we consider the problem of finding a locally optimal triangulation...

Incremental Algorithms for Finding the Convex Hulls of Circles and the Lower Envelopes of Parabolas (1995)

A Locally Optimal Triangulation of the Hyperbolic Paraboloid (1995)

The existing O(n log n) algorithms for finding the convex hulls of circles and the lower envelope of parabolas follow the divide-and-conquer paradigm. The difficulty with developing incremental...

Desnogues, Pascal, Devillers, Olivier

Given a set S of data points in R2 and corresponding data val ues for a specific non-convex surface, the unit hyperbolic paraboloid, we consider the problem of finding a locally optimal triangulation...

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

Revenge of the Dog: Queries on Voronoi Diagrams of Moving Points (1994)

Devillers, Olivier, Golin, Mordecai, Kedem, Klara, Schirra, Stefan

Suppose we are given $n$ moving postmen described by their motion equations $p_i(t) = s_i + v_it,$ $i=1,\ldots, n$, where $s_i \in \R^2$ is the position of the $i$'th postman at time $t=0$, and $v_i...

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

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

Revenge of the Dog: Queries on Voronoi Diagrams of Moving Points (1994)

Devillers, Olivier, Golin, Mordecai, Kedem, Klara, Schirra, Stefan

Suppose we are given $n$ moving postmen described by their motion equations $p_i(t) = s_i + v_it,$ $i=1,\ldots, n$, where $s_i \in \R^2$ is the position of the $i$'th postman at time $t=0$, and $v_i...

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

Incremental algorithms for finding the convex hulls of circles and the lower envelopes of parabolas (1994)

Dog bites postman: point location in the moving Voronoi diagram and related problems (1994)

The existing $O(n \log n)$ algorithms for finding the convex hulls of circles and the lower envelope of parabolas follow the divide-and-conquer paradigm. The difficulty with developing incremental...

Disponible dans les fichiers attachés à ce document

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

Revenge of the Dog: Queries on Voronoi Diagrams of Moving Points (1994)

Devillers, Olivier, Golin, Mordecai, Kedem, Klara, Schirra, Stefan

Suppose we are given $n$ moving postmen described by their motion equations $p_i(t) = s_i + v_it,$ $i=1,\ldots, n$, where $s_i \in \R^2$ is the position of the $i$'th postman at time $t=0$, and $v_i...

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

Incremental algorithms for finding the convex hulls of circles and the lower envelopes of parabolas (1994)

Dog bites postman: point location in the moving Voronoi diagram and related problems (1994)

The existing $O(n \log n)$ algorithms for finding the convex hulls of circles and the lower envelope of parabolas follow the divide-and-conquer paradigm. The difficulty with developing incremental...

Convex tours of bounded curvature (1994)

Disponible dans les fichiers attachés à ce document

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

Incremental algorithms for finding the convex hulls of circles and the lower envelopes of parabolas (1994)

Olivier Devillers, Mordecai J. Golin

Abstract: The existing O(n log n) algo rithms for nding the convex hulls of circles and the lower envelope of parabolas follow the di vide-and-conquer paradigm. The diOEculty with developing...

Revenge of the Dog: Queries on Voronoi Diagrams of Moving Points (1994)

Olivier Devillers, Olivier Devillers, Mordecai Golin, Mordecai Golin, Klara Kedem, Klara Kedem, ...

Suppose we are given n moving postmen described by their motion equations p i (t) = s i + v i t; i = 1, ..., n, where s i 2 IR 2 is the position of the i'th postman at time t = 0, and v i 2 IR 2...

Incremental Algorithms for Finding the Convex Hulls of Circles and the Lower Envelopes of Parabolas (1994)

Olivier Devillers Et, Olivier Devillers, Mordecai Golin, Mordecai Golin, Projet Prisme

: The existing O(n log n) algorithms for finding the convex hulls of circles and the lower envelope of parabolas follow the divide-and-conquer paradigm. The difficulty with developing incremental...

Dog Bites Postman: Point Location in the Moving Voronoi Diagram and Related Problems (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...

Olivier Devillers Et, Olivier Devillers, Mordecai Golin, Mordecai Golin, Projet Prisme

In this paper, we discuss two variations of the two-dimensional post-office problem that arise when the post-offices are n postmen moving with constant velocities. The first variation addresses the...

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

Revenge of the dog: Queries on Voronoi diagrams of moving points (1994)

Apport De Recherche, Olivier Devillers, Olivier Devillers, Mordecai Golin, Mordecai Golin, Klara Kedem, ...

Suppose we are given n moving postmen described by their motion equations p i #t#=s i + v i t; i =1;:::;n, where s i 2 IR is the position of the i'th postman at time t = 0, and v i 2 IR is his...

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

Scalable algorithms for bichromatic line segment intersection problems on coarse grained multicomputers (1993)

Devillers, Olivier, Fabri, A.

We present output-sensitive scalable parallel algorithms for bichromatic line segment intersection problems for the coarse grained multicomputer model. Under the assumption that n 3 p2, where n is...

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

Scalable algorithms for bichromatic line segment intersection problems on coarse grained multicomputers (1993)

Devillers, Olivier, Fabri, Andreas

We present output-sensitive scalable parallel algorithms for bichromatic line segment intersection problems for the coarse grained multicomputer model. Under the assumption that n 3 p2, where n is...

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

Scalable algorithms for bichromatic line segment intersection problems on coarse grained multicomputers (1993)

Devillers, Olivier, Fabri, Andreas

We present output-sensitive scalable parallel algorithms for bichromatic line segment intersection problems for the coarse grained multicomputer model. Under the assumption that n 3 p2, where n is...

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

Simultaneous Containment of Several Polygons: Analysis of the Contact Configurations (1993)

Simultaneous Containment of Several Polygons: Analysis of the Contact Configurations (1993)

The main concern of this paper is the detection of double contact configurations for some polygons moving in translation in a polygonal environment. We first establish some general properties about...

Randomisation, sphères et déplacements de robots (1993)

The main concern of this paper is the detection of double contact configurations for some polygons moving in translation in a polygonal environment. We first establish some general properties about...

Randomisation, sphères et déplacements de robots (1993)

Ce mémoire d'habilitation présente 14 articles différents, structurés en trois parties : algorithmes randomisés, algorithmes sur les sphères et placements de robots. Les algorithmes randomisés...

Randomisation, sphères et déplacements de robots (1993)

Ce mémoire d'habilitation présente 14 articles différents, structurés en trois parties : algorithmes randomisés, algorithmes sur les sphères et placements de robots. Les algorithmes randomisés...

Scalable Algorithms For Bichromatic Line Segment Intersection Problems On Coarse Grained Multicomputers (1993)

Ce mémoire d'habilitation présente 14 articles différents, structurés en trois parties : algorithmes randomisés, algorithmes sur les sphères et placements de robots. Les algorithmes randomisés...

E De Recherche, Route Des Lucioles, Olivier Devillers, Olivier Devillers, Andreas Fabri, Andreas Fabri

We present output-sensitive scalable parallel algorithms for bichromatic line segment intersection problems for the Coarse Grained Multicomputer model. Under the assumption that n p 2 , where n is...

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

Robust and efficient implementation of the Delaunay tree (1992)

The space of spheres, a geometric tool to unify duality results on Voronoi diagrams (1992)

In this paper, we present some practical results concerning the implementation of the algorithm described in (DMT) which computes dynamically the Delaunay triangulation of a set of sites in the plane...

Devillers, Olivier, Meiser, S., Teillaud, Monique

We present a framework that allows to easily derive transformations for various kinds of Voronoi and Power diagrams including k-th order and weighted versions. All proofs are essentially geometric...

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

Robust and efficient implementation of the Delaunay tree (1992)

The space of spheres, a geometric tool to unify duality results on Voronoi diagrams (1992)

In this paper, we present some practical results concerning the implementation of the algorithm described in (DMT) which computes dynamically the Delaunay triangulation of a set of sites in the plane...

Devillers, Olivier, Meiser, Stefan, Teillaud, Monique

We present a framework that allows to easily derive transformations for various kinds of Voronoi and Power diagrams including k-th order and weighted versions. All proofs are essentially geometric...

Fully dynamic Delaunay triangulation in logarithmic expected time per operation (1992)

Devillers, Olivier, Meiser, Stefan, Teillaud, Monique

The Delaunay Tree is a hierarchical data structure that has been introduced in \cite{BT} and analyzed in \cite{deltree,idag}. For a given set of sites S in the plane and an order of insertion for...

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

Fully dynamic Delaunay triangulation in logarithmic expected time per operation (1992)

Devillers, Olivier, Meiser, Stefan, Teillaud, Monique

The Delaunay Tree is a hierarchical data structure that has been introduced in \cite{BT} and analyzed in \cite{deltree,idag}. For a given set of sites S in the plane and an order of insertion for...

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

Robust and efficient implementation of the Delaunay tree (1992)

The space of spheres, a geometric tool to unify duality results on Voronoi diagrams (1992)

In this paper, we present some practical results concerning the implementation of the algorithm described in (DMT) which computes dynamically the Delaunay triangulation of a set of sites in the plane...

Devillers, Olivier, Meiser, Stefan, Teillaud, Monique

We present a framework that allows to easily derive transformations for various kinds of Voronoi and Power diagrams including k-th order and weighted versions. All proofs are essentially geometric...

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

Fully dynamic Delaunay triangulation in logarithmic expected time per operation (1992)

Devillers, Olivier, Meiser, Stefan, Teillaud, Monique

The Delaunay Tree is a hierarchical data structure that has been introduced in \cite{BT} and analyzed in \cite{deltree,idag}. For a given set of sites S in the plane and an order of insertion for...

Randomization Yields Simple O(n log* n) Algorithms for Difficult Omega(n) Problems (1992)

Randomization Yields Simple O(n log* n) Algorithms for Difficult Omega(n) Problems (1992)

We use here the results on the influence graph to adapt them for particular cases where additional information is available. In some cases, it is possible to improve the expected randomized...

Randomization yields simple O(n log n) algorithms for difcult (n) problems (1992)

We use here the results on the influence graph to adapt them for particular cases where additional information is available. In some cases, it is possible to improve the expected randomized...

Olivier Devillers, Communicated Kurt Mehlhorn

We use here the results on the influence graph 1 to adapt them for particular cases where additional information is available. In some cases, it is possible to improve the expected randomized...

Randomization Yields Simple O(n log* n) Algorithms for Difficult Omega(n) Problems (1992)

Olivier Devillers, Communicated Kurt Mehlhorn

We use here the results on the influence graph 1 to adapt them for particular cases where additional information is available. In some cases, it is possible to improve the expected randomized...

Robust and efficient implementation of the Delaunay tree (1992)

Del Aunay, Olivier Devillers

In this paper, we pr es ent s ome pr act i cal r es ul t s concer ni ng t he i mpl e - ment at i on of t he al gor i t hmdes cr i bed i n [DMT] whi ch comput es dynamicallytheDel aunay tr i angul at...

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

Dynamic location in an arrangement of line segments in the plane (1992)

Devillers, Olivier, Teillaud, Monique, Yvinec, Mariette

We describe in this paper an algorithm which dynamically maintains the trapezoidal map of an arrangement of line segments. This algorithm is a generalization of the Influence Graph data structure...

Dynamic location in an arrangement of line segments in the plane (1992)

Devillers, Olivier, Teillaud, Monique, Yvinec, Mariette

We describe in this paper an algorithm which dynamically maintains the trapezoidal map of an arrangement of line segments. This algorithm is a generalization of the Influence Graph data structure...

Dynamic location in an arrangement of line segments in the plane (1991)

Devillers, Olivier, Teillaud, Monique, Yvinec, Mariette

Randomization yields simple 0(n log\* n) algorithms for difficult (n) problems (1991)

Output sensitive construction of the 3D Delaunay triangulation of constrained sets of points (1991)

Boissonnat, Jean-Daniel, Cerezo, A., Devillers, Olivier, Teillaud, Monique

Dynamic location in an arrangement of line segments in the plane (1991)

Devillers, Olivier, Teillaud, Monique, Yvinec, Mariette

Disponible dans les fichiers attachés à ce document

Randomization yields simple 0(n log\* n) algorithms for difficult (n) problems (1991)

Output sensitive construction of the 3D Delaunay triangulation of constrained sets of points (1991)

Résumé disponible sur le PDF

Boissonnat, Jean-Daniel, Cerezo, André, Devillers, Olivier, Teillaud, Monique

Disponible dans les fichiers attachés à document

Dynamic location in an arrangement of line segments in the plane (1991)

Devillers, Olivier, Teillaud, Monique, Yvinec, Mariette

Disponible dans les fichiers attachés à ce document

Randomization yields simple 0(n log\* n) algorithms for difficult (n) problems (1991)

Output sensitive construction of the 3D Delaunay triangulation of constrained sets of points (1991)

Résumé disponible sur le PDF

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

Fully dynamic Delaunay triangulation in logarithmic expected time per operation (1990)

Devillers, Olivier, Meiser, S., Teillaud, Monique

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.

Simultaneous containment of several polygons : analysis of the contact configurations (1990)

Fully dynamic Delaunay triangulation in logarithmic expected time per operation (1990)

The main concern of this paper is the detetction of double-contact configurations for some polygons moving in translation in a polygonal environment. We first establish some general properties about...

Devillers, Olivier, Meiser, Stéphane, 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

Simultaneous containment of several polygons : analysis of the contact configurations (1990)

Fully dynamic Delaunay triangulation in logarithmic expected time per operation (1990)

The main concern of this paper is the detetction of double-contact configurations for some polygons moving in translation in a polygonal environment. We first establish some general properties about...

Devillers, Olivier, Meiser, Stéphane, 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

Simultaneous containment of several polygons : analysis of the contact configurations (1990)

Simultaneous Containment of Several Polygons: Analysis of the Contact Configurations (1990)

The main concern of this paper is the detetction of double-contact configurations for some polygons moving in translation in a polygonal environment. We first establish some general properties about...

Simultaneous Containment of Several Polygons: Analysis of the contact configurations (1990)

The main concern of this paper is the detection of double contact configurations for some polygons moving in translation in a polygonal environment. We first establish some general properties about...