Olivier Devillers

Proceedings of the 40th International Symposium on Computational Geometry, 2024

2023

Covering families of triangles.

[BibT_eX]

[DOI]

Period. Math. Hung., September, 2023

2021

Randomized Incremental Construction of Delaunay Triangulations of Nice Point Sets.

[BibT_eX]

[DOI]

Kunal Dutta

Marc Glisse

Discret. Comput. Geom., 2021

Stochastic Analysis of Empty-Region Graphs.

[BibT_eX]

Charles Duménil

Proceedings of the 33rd Canadian Conference on Computational Geometry, 2021

2020

Variable-width contouring for additive manufacturing.

[BibT_eX]

[DOI]

ACM Trans. Graph., 2020

Expected Complexity of Routing in $\Theta_6$ and Half-$\Theta_6$ Graphs.

[BibT_eX]

[DOI]

Prosenjit Bose

Jean-Lou De Carufel

J. Comput. Geom., 2020

Rounding Meshes in 3D.

[BibT_eX]

[DOI]

William J. Lenhart

Discret. Comput. Geom., 2020

2019

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

[BibT_eX]

[DOI]

Prosenjit Bose

Jean-Lou De Carufel

CoRR, 2019

Hardness results on Voronoi, Laguerre and Apollonius diagrams.

[BibT_eX]

Kevin Buchin

Menelaos Karavelas

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.

[BibT_eX]

[DOI]

Éric Fusy

J. Comput. Geom., 2018

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

[BibT_eX]

[DOI]

J. Comput. Geom., 2018

Walking in a Planar Poisson-Delaunay Triangulation: Shortcuts in the Voronoi Path.

[BibT_eX]

[DOI]

Louis Noizet

Int. J. Comput. Geom. Appl., 2018

Monotone Simultaneous Paths Embeddings in ℝd.

[BibT_eX]

[DOI]

Discret. Math. Theor. Comput. Sci., 2018

Expected Length of the Voronoi Path in a High Dimensional Poisson-Delaunay Triangulation.

[BibT_eX]

[DOI]

Discret. Comput. Geom., 2018

On Order Types of Random Point Sets.

[BibT_eX]

[DOI]

CoRR, 2018

Delaunay Triangulations of Points on Circles.

[BibT_eX]

[DOI]

CoRR, 2018

3D Snap Rounding.

[BibT_eX]

[DOI]

William J. Lenhart

Proceedings of the 34th International Symposium on Computational Geometry, 2018

2017

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

[BibT_eX]

[DOI]

Menelaos Karavelas

J. Comput. Geom., 2017

Celestial Walk: A Terminating Oblivious Walk for Convex Subdivisions.

[BibT_eX]

[DOI]

Wouter Kuijper

Victor Ermolaev

CoRR, 2017

2016

Delaunay Triangulation and Randomized Constructions.

[BibT_eX]

[DOI]

Encyclopedia of Algorithms, 2016

Triangulation Data Structures.

[BibT_eX]

[DOI]

Jarek Rossignac

Encyclopedia of Algorithms, 2016

Efficiently navigating a random Delaunay triangulation.

[BibT_eX]

[DOI]

Nicolas Broutin

Ross Hemsley

Random Struct. Algorithms, 2016

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

[BibT_eX]

[DOI]

Ross Hemsley

J. Comput. Geom., 2016

Smoothed complexity of convex hulls by witnesses and collectors.

[BibT_eX]

[DOI]

J. Comput. Geom., 2016

Recognizing shrinkable complexes is NP-complete.

[BibT_eX]

[DOI]

J. Comput. Geom., 2016

Monotone Simultaneous Embeddings of Paths in R^d.

[BibT_eX]

[DOI]

CoRR, 2016

Monotone Simultaneous Embeddings of Paths in d Dimensions.

[BibT_eX]

[DOI]

Proceedings of the Graph Drawing and Network Visualization - 24th International Symposium, 2016

Qualitative Symbolic Perturbation.

[BibT_eX]

[DOI]

Menelaos Karavelas

Proceedings of the 32nd International Symposium on Computational Geometry, 2016

2015

Guest Editors' Foreword.

[BibT_eX]

[DOI]

Siu-Wing Cheng

Discret. Comput. Geom., 2015

Homological reconstruction and simplification in R3.

[BibT_eX]

[DOI]

Comput. Geom., 2015

On the Smoothed Complexity of Convex Hulls.

[BibT_eX]

[DOI]

Proceedings of the 31st International Symposium on Computational Geometry, 2015

2014

Hyperbolic Delaunay Complexes and Voronoi Diagrams Made Practical.

[BibT_eX]

[DOI]

Mikhail Bogdanov

J. Comput. Geom., 2014

2013

Oja centers and centers of gravity.

[BibT_eX]

[DOI]

Comput. Geom., 2013

Practical distribution-sensitive point location in triangulations.

[BibT_eX]

[DOI]

Jonathan Richard Shewchuk

Comput. Aided Geom. Des., 2013

Vertex Deletion for 3D Delaunay Triangulations.

[BibT_eX]

[DOI]

Proceedings of the Algorithms - ESA 2013, 2013

Complexity analysis of random geometric structures made simpler.

[BibT_eX]

[DOI]

Marc Glisse

Xavier Goaoc

Proceedings of the Symposium on Computational Geometry 2013, 2013

2012

A Tight Bound for the Delaunay Triangulation of Points on a Polyhedron.

[BibT_eX]

[DOI]

Nina Amenta

Dominique Attali

Discret. Comput. Geom., 2012

The monotonicity of f-vectors of random polytopes

[BibT_eX]

[DOI]

CoRR, 2012

ESQ: Editable SQuad Representation for Triangle Meshes.

[BibT_eX]

[DOI]

Jarek Rossignac

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.

[BibT_eX]

[DOI]

Éric Fusy

Proceedings of the Graph Drawing - 20th International Symposium, 2012

2011

On the asymptotic growth rate of some spanning trees embedded in Rd.

[BibT_eX]

[DOI]

Oper. Res. Lett., 2011

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

[BibT_eX]

[DOI]

J. Comput. Geom., 2011

Catalog-Based Representation of 2D Triangulations.

[BibT_eX]

[DOI]

Abdelkrim Mebarki

Int. J. Comput. Geom. Appl., 2011

Perturbations for Delaunay and weighted Delaunay 3D triangulations.

[BibT_eX]

[DOI]

Comput. Geom., 2011

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

[BibT_eX]

[DOI]

Comput. Geom., 2011

Explicit Array-Based Compact Data Structures for Triangulations.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Computation - 22nd International Symposium, 2011

A pedagogic JavaScript program for point location strategies.

[BibT_eX]

[DOI]

Proceedings of the 27th ACM Symposium on Computational Geometry, 2011

Simple and Efficient Distribution-Sensitive Point Location, in Triangulations.

[BibT_eX]

[DOI]

Proceedings of the Thirteenth Workshop on Algorithm Engineering and Experiments, 2011

2010

Oja medians and centers of gravity.

[BibT_eX]

[DOI]

Proceedings of the 22nd Annual Canadian Conference on Computational Geometry, 2010

2009

Helly-Type Theorems for Approximate Covering.

[BibT_eX]

[DOI]

Discret. Comput. Geom., 2009

On the complexity of umbra and penumbra.

[BibT_eX]

[DOI]

Comput. Geom., 2009

Filtering Relocations on a Delaunay Triangulation.

[BibT_eX]

[DOI]

Jane Tournois

Comput. Graph. Forum, 2009

Incremental construction of the delaunay triangulation and the delaunay graph in medium dimension.

[BibT_eX]

[DOI]

Samuel Hornus

Proceedings of the 25th ACM Symposium on Computational Geometry, 2009

2008

Succinct representations of planar maps.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2008

Empty-ellipse graphs.

[BibT_eX]

[DOI]

Jeff Erickson

Xavier Goaoc

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.

[BibT_eX]

[DOI]

Marc Glisse

Proceedings of the 24th ACM Symposium on Computational Geometry, 2008

2007

Lines and Free Line Segments Tangent to Arbitrary Three-Dimensional Convex Polyhedra.

[BibT_eX]

[DOI]

SIAM J. Comput., 2007

Maintaining Visibility Information of Planar Point Sets with a Moving Viewpoint.

[BibT_eX]

[DOI]

Int. J. Comput. Geom. Appl., 2007

Lines Tangent to Four Triangles in Three-Dimensional Space.

[BibT_eX]

[DOI]

Discret. Comput. Geom., 2007

Complexity of Delaunay triangulation for points on lower-dimensional polyhedra.

[BibT_eX]

[DOI]

Nina Amenta

Dominique Attali

Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

Interleaving Delaunay Refinement and Optimization for 2D Triangle Mesh Generation.

[BibT_eX]

[DOI]

Jane Tournois

Proceedings of the 16th International Meshing Roundtable, 2007

Between umbra and penumbra.

[BibT_eX]

[DOI]

Proceedings of the 23rd ACM Symposium on Computational Geometry, 2007

2006

Drawing Kn in Three Dimensions with One Bend per Edge.

[BibT_eX]

[DOI]

J. Graph Algorithms Appl., 2006

Inner and outer rounding of Boolean operations on lattice polygonal regions.

[BibT_eX]

[DOI]

Comput. Geom., 2006

Optimal succinct representations of planar maps.

[BibT_eX]

[DOI]

Proceedings of the 22nd ACM Symposium on Computational Geometry, 2006

2D Triangulation Representation Using Stable Catalogs.

[BibT_eX]

[DOI]

Abdelkrim Mebarki

Proceedings of the 18th Annual Canadian Conference on Computational Geometry, 2006

2005

Centroidal Voronoi diagrams for isotropic surface remeshing.

[BibT_eX]

[DOI]

Éric Colin de Verdière

Martin Isenburg

Graph. Model., 2005

Succinct Representation of Triangulations with a Boundary.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Data Structures, 9th International Workshop, 2005

Farthest Point Seeding for Efficient Placement of Streamlines.

[BibT_eX]

[DOI]

Abdelkrim Mebarki

Proceedings of the 16th IEEE Visualization Conference, 2005

Drawing Kn in Three Dimensions with One Bend Per Edge.

[BibT_eX]

[DOI]

Proceedings of the Graph Drawing, 13th International Symposium, 2005

Dynamic updates of succinct triangulations.

[BibT_eX]

[DOI]

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

2004

Inner and outer rounding of set operations on lattice polygonal regions.

[BibT_eX]

[DOI]

Proceedings of the 20th ACM Symposium on Computational Geometry, 2004

The number of lines tangent to arbitrary convex polyhedra in 3D.

[BibT_eX]

[DOI]

Proceedings of the 20th ACM Symposium on Computational Geometry, 2004

On the number of line tangents to four triangles in three-dimensional space.

[BibT_eX]

[DOI]

Proceedings of the 16th Canadian Conference on Computational Geometry, 2004

2003

Anisotropic polygonal remeshing.

[BibT_eX]

[DOI]

ACM Trans. Graph., 2003

The Expected Number of 3D Visibility Events Is Linear.

[BibT_eX]

[DOI]

SIAM J. Comput., 2003

Fast and Robust Triangle-Triangle Overlap Test Using Orientation Predicates.

[BibT_eX]

[DOI]

J. Graphics, GPU, & Game Tools, 2003

Culling a Set of Points for Roundness or Cylindricity Evaluations.

[BibT_eX]

[DOI]

Int. J. Comput. Geom. Appl., 2003

Minimal Set of Constraints for 2D Constrained Delaunay Reconstruction.

[BibT_eX]

[DOI]

Int. J. Comput. Geom. Appl., 2003

The Number of Cylindrical Shells.

[BibT_eX]

[DOI]

Discret. Comput. Geom., 2003

Circular Cylinders through Four or Five Points in Space.

[BibT_eX]

[DOI]

Discret. Comput. Geom., 2003

Chromatic variants of the Erdsos-CSzekeres theorem on points in convex position.

[BibT_eX]

[DOI]

Comput. Geom., 2003

Perturbations and vertex removal in a 3D delaunay triangulation.

[BibT_eX]

[DOI]

Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2003

Isotropic Surface Remeshing.

[BibT_eX]

[DOI]

Éric Colin de Verdière

Martin Isenburg

Proceedings of the 2003 International Conference on Shape Modeling and Applications (SMI 2003), 2003

Efficient Exact Geometric Predicates for Delauny Triangulations.

[BibT_eX]

Sylvain Pion

Proceedings of the Fifth Workshop on Algorithm Engineering and Experiments, 2003

2002

Progressive lossless compression of arbitrary simplicial complexes.

[BibT_eX]

[DOI]

ACM Trans. Graph., 2002

Rounding Voronoi diagram.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2002

Walking in a Triangulation.

[BibT_eX]

[DOI]

Sylvain Pion

Int. J. Found. Comput. Sci., 2002

The Delaunay Hierarchy.

[BibT_eX]

[DOI]

Int. J. Found. Comput. Sci., 2002

Computing Roundness is Easy if the Set is Almost Round.

[BibT_eX]

[DOI]

Pedro A. Ramos

Int. J. Comput. Geom. Appl., 2002

On Deletion in Delaunay Triangulations.

[BibT_eX]

[DOI]

Int. J. Comput. Geom. Appl., 2002

Algebraic methods and arithmetic filtering for exact predicates on circle arcs.

[BibT_eX]

[DOI]

Comput. Geom., 2002

Triangulations in CGAL.

[BibT_eX]

[DOI]

Comput. Geom., 2002

Splitting a Delaunay Triangulation in Linear Time.

[BibT_eX]

[DOI]

Algorithmica, 2002

On the number of lines tangent to four convex polyhedra.

[BibT_eX]

[DOI]

Proceedings of the 14th Canadian Conference on Computational Geometry, 2002

2001

The Shuffling Buffer.

[BibT_eX]

[DOI]

Int. J. Comput. Geom. Appl., 2001

Circular Separability of Polygons.

[BibT_eX]

[DOI]

Jurek Czyzowicz

Algorithmica, 2001

Separating several point sets in the plane.

[BibT_eX]

[DOI]

Proceedings of the 13th Canadian Conference on Computational Geometry, 2001

2000

Motion Planning of Legged Robots.

[BibT_eX]

[DOI]

SIAM J. Comput., 2000

Removing Degeneracies by Perturbing the Problem or Perturbing the World.

[BibT_eX]

[DOI]

Jack Snoeyink

Reliab. Comput., 2000

Computing Largest Circles Separating Two Sets of Segments.

[BibT_eX]

[DOI]

Int. J. Comput. Geom. Appl., 2000

Geometric compression for interactive transmission.

[BibT_eX]

[DOI]

Proceedings of the 11th IEEE Visualization Conference, 2000

Evaluating the cylindricity of a nominally cylindrical point set.

[BibT_eX]

[DOI]

Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2000

Triangulations in CGAL (extended abstract).

[BibT_eX]

[DOI]

Proceedings of the Sixteenth Annual Symposium on Computational Geometry, 2000

1999

Finding an Ordinary Conic and an Ordinary Hyperplane.

[BibT_eX]

Asish Mukhopadhyay

Nord. J. Comput., 1999

Optimal Line Bipartitions of Point Sets.

[BibT_eX]

[DOI]

Matthew J. Katz

Int. J. Comput. Geom. Appl., 1999

Geometric compression for progressive transmission

[BibT_eX]

[DOI]

CoRR, 1999

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

[BibT_eX]

[DOI]

Hervé Brönnimann

CoRR, 1999

On Deletion in Delaunay Triangulation

[BibT_eX]

[DOI]

CoRR, 1999

Further results on arithmetic filters for geometric predicates.

[BibT_eX]

[DOI]

Comput. Geom., 1999

Convex tours of bounded curvature.

[BibT_eX]

[DOI]

Comput. Geom., 1999

Programming with CGAL: The Example of Triangulations.

[BibT_eX]

[DOI]

Proceedings of the Fifteenth Annual Symposium on Computational Geometry, 1999

1998

Computing the Maximum Overlap of Two Convex Polygons under Translations.

[BibT_eX]

[DOI]

Theory Comput. Syst., 1998

Dog Bites Postman: Point Location in the Moving Voronoi Diagram and Related Problems.

[BibT_eX]

[DOI]

Mordecai J. Golin

Int. J. Comput. Geom. Appl., 1998

A Probabilistic Analysis of the Power of Arithmetic Filters.

[BibT_eX]

[DOI]

Discret. Comput. Geom., 1998

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

[BibT_eX]

[DOI]

CoRR, 1998

Checking the convexity of polytopes and the planarity of subdivisions.

[BibT_eX]

[DOI]

Comput. Geom., 1998

Improved Incremental Randomized Delaunay Triangulation.

[BibT_eX]

[DOI]

Proceedings of the Fourteenth Annual Symposium on Computational Geometry, 1998

1997

Computing a Single Cell in the Overlay of Two Simple Polygons.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1997

Evaluating Signs of Determinants Using Single-Precision Arithmetic.

[BibT_eX]

[DOI]

Francis Avnaim

Algorithmica, 1997

Checking the Convexity of Polytopes and the Planarity of Subdivisions (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Data Structures, 5th International Workshop, 1997

1996

An Introduction to Randomization in Computational Geometry.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1996

Scalable algorithms for bichromatic line segment intersection problems on coarse grained multicomputers.

[BibT_eX]

[DOI]

Andreas Fabri

Int. J. Comput. Geom. Appl., 1996

Output-sensitive construction of the {Delaunay} triangulation of points lying in two planes.

[BibT_eX]

[DOI]

André Cérézo

Int. J. Comput. Geom. Appl., 1996

Queries on Voronoi Diagrams of Moving Points.

[BibT_eX]

[DOI]

Comput. Geom., 1996

An Algorithm for Constructing the Convex Hull of a Set of Spheres in Dimension D.

[BibT_eX]

[DOI]

Comput. Geom., 1996

Computational geometry and discrete computations.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Mordecai J. Golin

Inf. Process. Lett., 1995

Motion planning of legged robots: the spider robot problem.

[BibT_eX]

[DOI]

LeonBattista Donati

Int. J. Comput. Geom. Appl., 1995

Circular Separability of Polygon.

[BibT_eX]

[DOI]

Jurek Czyzowicz

Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 1995

Evaluation of a New Method to Compute Signs of Determinants.

[BibT_eX]

[DOI]

Francis Avnaim

Proceedings of the Eleventh Annual Symposium on Computational Geometry, 1995

A locally optimal triangulation of the hyperbolic paraboloid.

[BibT_eX]

[DOI]

Pascal Desnoguès

Proceedings of the 7th Canadian Conference on Computational Geometry, 1995

1994

From Spider Robots to Half Disk Robots.

[BibT_eX]

[DOI]

Proceedings of the 1994 International Conference on Robotics and Automation, 1994

Revenge of the Dog: Queries on Voronoi Diagrams of Moving Points.

[BibT_eX]

Proceedings of the 6th Canadian Conference on Computational Geometry, 1994

1993

Simultaneous containment of several polygons: analysis of the contact configurations.

[BibT_eX]

[DOI]

Int. J. Comput. Geom. Appl., 1993

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

[BibT_eX]

[DOI]

Algorithmica, 1993

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

[BibT_eX]

[DOI]

, 1993

1992

Randomization yields simple O(n log* n) algorithms for difficult Omega(n) problems.

[BibT_eX]

[DOI]

Int. J. Comput. Geom. Appl., 1992

Applications of Random Sampling to On-line Algorithms in Computational Geometry.

[BibT_eX]

[DOI]

Discret. Comput. Geom., 1992

Fully Dynamic Delaunay Triangulation in Logarithmic Expected Time Per Operation.

[BibT_eX]

[DOI]

Stefan Meiser

Comput. Geom., 1992

Motion planning for spider robots.

[BibT_eX]

[DOI]

LeonBattista Donati

Proceedings of the 1992 IEEE International Conference on Robotics and Automation, 1992

Stable Placements for Spider Robots.

[BibT_eX]

[DOI]

LeonBattista Donati

Proceedings of the Eighth Annual Symposium on Computational Geometry, 1992

1991

Computing the union of 3-colored triangles.

[BibT_eX]

[DOI]

Int. J. Comput. Geom. Appl., 1991

Fully Dynamic Delauney Triangulation in Logarithmic Expected Time per Operation.

[BibT_eX]

[DOI]

Stefan Meiser

Proceedings of the Algorithms and Data Structures, 1991

1989

The Macro-Regions: An Efficient Space Subdivision Structure for Ray Tracing.

[BibT_eX]

[DOI]

Proceedings of the 10th European Computer Graphics Conference and Exhibition, 1989

1988

Méthodes d'optimisation du tracé de rayons.

[BibT_eX]

[DOI]