111 citations · 167 across the 20 of their papers we have counts for
21 papers
Expected Complexity of Routing in 6 and Half- 6 Graphs
Prosenjit Bose, Jean-Lou de Carufel, Olivier Devillers
We study online routing algorithms on the 6-graph and the half-6-graph (which is equivalent to a variant of the Delaunay triangulation). Given a source vertex s and a target…
On Order Types of Random Point Sets
Olivier Devillers, Philippe Duchon, Marc Glisse +1
A simple method to produce a random order type is to take the order type of a random point set. We conjecture that many probability distributions on order types defined in this way…
Delaunay Triangulations of Points on Circles
Vincent Despré, Olivier Devillers, Hugo Parlier +1
Delaunay triangulations of a point set in the Euclidean plane are ubiquitous in a number of computational sciences, including computational geometry. Delaunay triangulations are no…
Celestial Walk: A Terminating Oblivious Walk for Convex Subdivisions
Wouter Kuijper, Victor Ermolaev, Olivier Devillers
We present a new oblivious walking strategy for convex subdivisions. Our walk is faster than the straight walk and more generally applicable than the visibility walk. To prove term…
Monotone Simultaneous Embeddings of Paths in R^d
David Bremner, Olivier Devillers, Marc Glisse +5
We study the following problem: Given paths that share the same vertex set, is there a simultaneous geometric embedding of these paths such that each individual drawing is mono…
Stretch Factor of Long Paths in a planar Poisson-Delaunay Triangulation
Nicolas Chenavier, Olivier Devillers
Let , where is a planar Poisson point process of intensity . We provide a first non-trivial lower bound for the distance between the expected le…