CNRS, Loria
Université de Lorraine
The talk will present two problems mixing computational geometry and probability.
The first part is about the witness/collector method for smoothed analysis. We present a simple technique for analyzing the size of geometric hyper graphs defined by random point sets. As an application we obtain upper and lower bounds on the smoothed number of faces of the convex hull under Euclidean and Gaussian noise and related results.
The second part study the length of several paths in the Delaunay triangulation between two points at unit distance. The point set is defined as a planar Poisson point process of density going to infinity. We prove that the “upper path” has expected length converging to $1.18$ and that the shortest path cannot be smaller than $1+10^{-11}$.
Related paper, smoothed analysis:
Related papers, walking in random Delaunay triangulation: