111 citations · 167 across the 20 of their papers we have counts for
16 papers · 1 filter
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…
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…
The monotonicity of f-vectors of random polytopes
Olivier Devillers, Marc Glisse, Xavier Goaoc +2
Let K be a compact convex body in Rd, let Kn be the convex hull of n points chosen uniformly and independently in K, and let fi(Kn) denote the number of i-dimensional faces of Kn.…
Inner and Outer Rounding of Boolean Operations on Lattice Polygonal Regions
Olivier Devillers, Philippe Guigue
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 implementati…