# Olivier Devillers

According to our database1, Olivier Devillers authored at least 140 papers between 1988 and 2020.

Collaborative distances:

Book
In proceedings
Article
PhD thesis
Other

## Bibliography

2020
Rounding Meshes in 3D.
Discret. Comput. Geom., 2020

2019
Expected Complexity of Routing in $Θ$ 6 and Half-$Θ$ 6 Graphs.
CoRR, 2019

Randomized Incremental Construction of Delaunay Triangulations of Nice Point Sets.
Proceedings of the 27th Annual European Symposium on Algorithms, 2019

Hardness results on Voronoi, Laguerre and Apollonius diagrams.
Proceedings of the 31st Canadian Conference on Computational Geometry, 2019

2018
Canonical ordering for graphs on the cylinder, with applications to periodic straight-line drawings on the flat cyclinder and torus.
JoCG, 2018

Array-based compact data structures for triangulations: Practical solutions with theoretical guarantees.
JoCG, 2018

Walking in a Planar Poisson-Delaunay Triangulation: Shortcuts in the Voronoi Path.
Int. J. Comput. Geom. Appl., 2018

Monotone Simultaneous Paths Embeddings in ℝ<sup>d</sup>.
Discret. Math. Theor. Comput. Sci., 2018

Expected Length of the Voronoi Path in a High Dimensional Poisson-Delaunay Triangulation.
Discret. Comput. Geom., 2018

On Order Types of Random Point Sets.
CoRR, 2018

Delaunay Triangulations of Points on Circles.
CoRR, 2018

3D Snap Rounding.
Proceedings of the 34th International Symposium on Computational Geometry, 2018

2017
Qualitative symbolic perturbation: two applications of a new geometry-based perturbation framework.
JoCG, 2017

Celestial Walk: A Terminating Oblivious Walk for Convex Subdivisions.
CoRR, 2017

2016
Delaunay Triangulation and Randomized Constructions.
Encyclopedia of Algorithms, 2016

Triangulation Data Structures.
Encyclopedia of Algorithms, 2016

Efficiently navigating a random Delaunay triangulation.
Random Struct. Algorithms, 2016

The worst visibility walk in a random Delaunay triangulation is $O(\sqrt{n})$.
JoCG, 2016

Smoothed complexity of convex hulls by witnesses and collectors.
JoCG, 2016

Recognizing shrinkable complexes is NP-complete.
JoCG, 2016

Monotone Simultaneous Embeddings of Paths in R^d.
CoRR, 2016

Monotone Simultaneous Embeddings of Paths in d Dimensions.
Proceedings of the Graph Drawing and Network Visualization, 2016

Qualitative Symbolic Perturbation.
Proceedings of the 32nd International Symposium on Computational Geometry, 2016

2015
Guest Editors' Foreword.
JoCG, 2015

Homological reconstruction and simplification in R<sup>3</sup>.
Comput. Geom., 2015

On the Smoothed Complexity of Convex Hulls.
Proceedings of the 31st International Symposium on Computational Geometry, 2015

2014
Hyperbolic Delaunay Complexes and Voronoi Diagrams Made Practical.
JoCG, 2014

2013
Oja centers and centers of gravity.
Comput. Geom., 2013

Practical distribution-sensitive point location in triangulations.
Comput. Aided Geom. Des., 2013

Vertex Deletion for 3D Delaunay Triangulations.
Proceedings of the Algorithms - ESA 2013, 2013

Complexity analysis of random geometric structures made simpler.
Proceedings of the Symposuim on Computational Geometry 2013, 2013

2012
A Tight Bound for the Delaunay Triangulation of Points on a Polyhedron.
Discret. Comput. Geom., 2012

The monotonicity of f-vectors of random polytopes
CoRR, 2012

ESQ: Editable SQuad Representation for Triangle Meshes.
Proceedings of the 25th SIBGRAPI Conference on Graphics, Patterns and Images, 2012

Canonical Ordering for Triangulations on the Cylinder, with Applications to Periodic Straight-Line Drawings.
Proceedings of the Graph Drawing - 20th International Symposium, 2012

2011
On the asymptotic growth rate of some spanning trees embedded in R<sup>d</sup>.
Oper. Res. Lett., 2011

Delaunay Triangulation of Imprecise Points, Preprocess and Actually Get a Fast Query Time.
JoCG, 2011

Catalog-Based Representation of 2D Triangulations.
Int. J. Comput. Geom. Appl., 2011

Perturbations for Delaunay and weighted Delaunay 3D triangulations.
Comput. Geom., 2011

Vertex removal in two-dimensional Delaunay triangulation: Speed-up by low degrees optimization.
Comput. Geom., 2011

Explicit Array-Based Compact Data Structures for Triangulations.
Proceedings of the Algorithms and Computation - 22nd International Symposium, 2011

A pedagogic JavaScript program for point location strategies.
Proceedings of the 27th ACM Symposium on Computational Geometry, 2011

Simple and Efficient Distribution-Sensitive Point Location, in Triangulations.
Proceedings of the Thirteenth Workshop on Algorithm Engineering and Experiments, 2011

2010
Oja medians and centers of gravity.
Proceedings of the 22nd Annual Canadian Conference on Computational Geometry, 2010

2009
Helly-Type Theorems for Approximate Covering.
Discret. Comput. Geom., 2009

On the complexity of umbra and penumbra.
Comput. Geom., 2009

Filtering Relocations on a Delaunay Triangulation.
Comput. Graph. Forum, 2009

Incremental construction of the delaunay triangulation and the delaunay graph in medium dimension.
Proceedings of the 25th ACM Symposium on Computational Geometry, 2009

2008
Succinct representations of planar maps.
Theor. Comput. Sci., 2008

Empty-ellipse graphs.
Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

Predicates for line transversals to lines and line segments in three-dimensional space.
Proceedings of the 24th ACM Symposium on Computational Geometry, 2008

2007
Lines and Free Line Segments Tangent to Arbitrary Three-Dimensional Convex Polyhedra.
SIAM J. Comput., 2007

Maintaining Visibility Information of Planar Point Sets with a Moving Viewpoint.
Int. J. Comput. Geom. Appl., 2007

Lines Tangent to Four Triangles in Three-Dimensional Space.
Discret. Comput. Geom., 2007

Complexity of Delaunay triangulation for points on lower-dimensional polyhedra.
Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

Interleaving Delaunay Refinement and Optimization for 2D Triangle Mesh Generation.
Proceedings of the 16th International Meshing Roundtable, 2007

Between umbra and penumbra.
Proceedings of the 23rd ACM Symposium on Computational Geometry, Gyeongju, 2007

2006
Drawing Kn in Three Dimensions with One Bend per Edge.
J. Graph Algorithms Appl., 2006

Inner and outer rounding of Boolean operations on lattice polygonal regions.
Comput. Geom., 2006

Optimal succinct representations of planar maps.
Proceedings of the 22nd ACM Symposium on Computational Geometry, 2006

2D Triangulation Representation Using Stable Catalogs.
Proceedings of the 18th Annual Canadian Conference on Computational Geometry, 2006

2005
Centroidal Voronoi diagrams for isotropic surface remeshing.
Graph. Model., 2005

Succinct Representation of Triangulations with a Boundary.
Proceedings of the Algorithms and Data Structures, 9th International Workshop, 2005

Farthest Point Seeding for Efficient Placement of Streamlines.
Proceedings of the 16th IEEE Visualization Conference, 2005

Drawing <i>K</i><sub><i>n</i></sub> in Three Dimensions with One Bend Per Edge.
Proceedings of the Graph Drawing, 13th International Symposium, 2005

Proceedings of the 17th Canadian Conference on Computational Geometry, 2005

2004
Inner and outer rounding of set operations on lattice polygonal regions.
Proceedings of the 20th ACM Symposium on Computational Geometry, 2004

The number of lines tangent to arbitrary convex polyhedra in 3D.
Proceedings of the 20th ACM Symposium on Computational Geometry, 2004

On the number of line tangents to four triangles in three-dimensional space.
Proceedings of the 16th Canadian Conference on Computational Geometry, 2004

2003
Anisotropic polygonal remeshing.
ACM Trans. Graph., 2003

The Expected Number of 3D Visibility Events Is Linear.
SIAM J. Comput., 2003

Fast and Robust Triangle-Triangle Overlap Test Using Orientation Predicates.
J. Graphics, GPU, & Game Tools, 2003

Culling a Set of Points for Roundness or Cylindricity Evaluations.
Int. J. Comput. Geom. Appl., 2003

Minimal Set of Constraints for 2D Constrained Delaunay Reconstruction.
Int. J. Comput. Geom. Appl., 2003

The Number of Cylindrical Shells.
Discret. Comput. Geom., 2003

Chromatic variants of the Erdsos-CSzekeres theorem on points in convex position.
Comput. Geom., 2003

Perturbations and vertex removal in a 3D delaunay triangulation.
Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2003

Isotropic Surface Remeshing.
Proceedings of the 2003 International Conference on Shape Modeling and Applications (SMI 2003), 2003

Efficient Exact Geometric Predicates for Delauny Triangulations.
Proceedings of the Fifth Workshop on Algorithm Engineering and Experiments, 2003

2002
Progressive lossless compression of arbitrary simplicial complexes.
ACM Trans. Graph., 2002

Rounding Voronoi diagram.
Theor. Comput. Sci., 2002

Walking in a Triangulation.
Int. J. Found. Comput. Sci., 2002

The Delaunay Hierarchy.
Int. J. Found. Comput. Sci., 2002

Computing Roundness is Easy if the Set is Almost Round.
Int. J. Comput. Geom. Appl., 2002

On Deletion in Delaunay Triangulations.
Int. J. Comput. Geom. Appl., 2002

Algebraic methods and arithmetic filtering for exact predicates on circle arcs.
Comput. Geom., 2002

Triangulations in CGAL.
Comput. Geom., 2002

Splitting a Delaunay Triangulation in Linear Time.
Algorithmica, 2002

On the number of lines tangent to four convex polyhedra.
Proceedings of the 14th Canadian Conference on Computational Geometry, 2002

2001
The Shuffling Buffer.
Int. J. Comput. Geom. Appl., 2001

Circular Separability of Polygons.
Algorithmica, 2001

Separating several point sets in the plane.
Proceedings of the 13th Canadian Conference on Computational Geometry, 2001

2000
Motion Planning of Legged Robots.
SIAM J. Comput., 2000

Removing Degeneracies by Perturbing the Problem or Perturbing the World.
Reliab. Comput., 2000

Computing Largest Circles Separating Two Sets of Segments.
Int. J. Comput. Geom. Appl., 2000

Geometric compression for interactive transmission.
Proceedings of the IEEE Visualization 2000, 2000

Evaluating the cylindricity of a nominally cylindrical point set.
Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2000

Triangulations in CGAL (extended abstract).
Proceedings of the Sixteenth Annual Symposium on Computational Geometry, 2000

1999
Finding an Ordinary Conic and an Ordinary Hyperplane.
Nord. J. Comput., 1999

Optimal Line Bipartitions of Point Sets.
Int. J. Comput. Geom. Appl., 1999

Geometric compression for progressive transmission
CoRR, 1999

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

On Deletion in Delaunay Triangulation
CoRR, 1999

Further results on arithmetic filters for geometric predicates.
Comput. Geom., 1999

Convex tours of bounded curvature.
Comput. Geom., 1999

Programming with CGAL: The Example of Triangulations.
Proceedings of the Fifteenth Annual Symposium on Computational Geometry, 1999

1998
Computing the Maximum Overlap of Two Convex Polygons under Translations.
Theory Comput. Syst., 1998

Dog Bites Postman: Point Location in the Moving Voronoi Diagram and Related Problems.
Int. J. Comput. Geom. Appl., 1998

A Probabilistic Analysis of the Power of Arithmetic Filters.
Discret. Comput. Geom., 1998

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

Checking the convexity of polytopes and the planarity of subdivisions.
Comput. Geom., 1998

Improved Incremental Randomized Delaunay Triangulation.
Proceedings of the Fourteenth Annual Symposium on Computational Geometry, 1998

1997
Computing a Single Cell in the Overlay of Two Simple Polygons.
Inf. Process. Lett., 1997

Evaluating Signs of Determinants Using Single-Precision Arithmetic.
Algorithmica, 1997

Checking the Convexity of Polytopes and the Planarity of Subdivisions (Extended Abstract).
Proceedings of the Algorithms and Data Structures, 5th International Workshop, 1997

1996
An Introduction to Randomization in Computational Geometry.
Theor. Comput. Sci., 1996

Scalable algorithms for bichromatic line segment intersection problems on coarse grained multicomputers.
Int. J. Comput. Geom. Appl., 1996

Output-sensitive construction of the {Delaunay} triangulation of points lying in two planes.
Int. J. Comput. Geom. Appl., 1996

Queries on Voronoi Diagrams of Moving Points.
Comput. Geom., 1996

An Algorithm for Constructing the Convex Hull of a Set of Spheres in Dimension D.
Comput. Geom., 1996

Computational geometry and discrete computations.
Proceedings of the Discrete Geometry for Computer Imagery, 1996

1995
Incremental Algorithms for Finding the Convex Hulls of Circles and the Lower Envelopes of Parabolas.
Inf. Process. Lett., 1995

Motion planning of legged robots: the spider robot problem.
Int. J. Comput. Geom. Appl., 1995

Circular Separability of Polygon.
Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 1995

Evaluation of a New Method to Compute Signs of Determinants.
Proceedings of the Eleventh Annual Symposium on Computational Geometry, 1995

A locally optimal triangulation of the hyperbolic paraboloid.
Proceedings of the 7th Canadian Conference on Computational Geometry, 1995

1994
From Spider Robots to Half Disk Robots.
Proceedings of the 1994 International Conference on Robotics and Automation, 1994

Revenge of the Dog: Queries on Voronoi Diagrams of Moving Points.
Proceedings of the 6th Canadian Conference on Computational Geometry, 1994

1993
Simultaneous containment of several polygons: analysis of the contact configurations.
Int. J. Comput. Geom. Appl., 1993

A Semidynamic Construction of Higher-Order Voronoi Diagrams and Its Randomized Analysis.
Algorithmica, 1993

Randomisation, sphères et déplacements de robots.
, 1993

1992
Randomization yields simple O(n log<sup>*</sup> n) algorithms for difficult Omega(n) problems.
Int. J. Comput. Geom. Appl., 1992

Applications of Random Sampling to On-line Algorithms in Computational Geometry.
Discret. Comput. Geom., 1992

Fully Dynamic Delaunay Triangulation in Logarithmic Expected Time Per Operation.
Comput. Geom., 1992

Motion planning for spider robots.
Proceedings of the 1992 IEEE International Conference on Robotics and Automation, 1992

Stable Placements for Spider Robots.
Proceedings of the Eighth Annual Symposium on Computational Geometry, 1992

1991
Computing the union of 3-colored triangles.
Int. J. Comput. Geom. Appl., 1991

Fully Dynamic Delauney Triangulation in Logarithmic Expected Time per Operation.
Proceedings of the Algorithms and Data Structures, 1991

1989
The Macro-Regions: An Efficient Space Subdivision Structure for Ray Tracing.
Proceedings of the 10th European Computer Graphics Conference and Exhibition, 1989

1988
Méthodes d'optimisation du tracé de rayons.
PhD thesis, 1988