Probabilistic methods for the analysis of algorithms on random tessellations

Ross Hemsley 1
1 GEOMETRICA - Geometric computing
CRISAM - Inria Sophia Antipolis - Méditerranée , Inria Saclay - Ile de France
Abstract : In this thesis, we leverage the tools of probability theory and stochastic geometry to investigate the behavior of algorithms on geometric tessellations of space. This work is split between two main themes, the first of which is focused on the problem of navigating the Delaunay tessellation and its geometric dual, the Voronoi diagram. We explore the applications of this problem to point location using walking algorithms and the study of online routing in networks. We then propose and investigate two new algorithms which navigate the Delaunay triangulation, which we call Pivot Walk and Cone Walk. For Cone Walk, we provide a detailed average-case analysis, giving explicit bounds on the properties of the worst possible path taken by the algorithm on a random Delaunay triangulation in a bounded convex region. This analysis is a significant departure from similar results that have been obtained, due to the difficulty of dealing with the complex dependence structure of localized navigation algorithms on the Delaunay triangulation. The second part of this work is concerned with the study of extremal properties of random tessellations. In particular, we derive the first and last order-statistics for the inballs of the cells in a Poisson line tessellation. This result has implications for algorithms involving line tessellations, such as locality sensitive hashing. As a corollary, we show that the cells minimizing the area are triangles.
Document type :
Liste complète des métadonnées

Cited literature [114 references]  Display  Hide  Download
Contributor : Abes Star <>
Submitted on : Thursday, April 9, 2015 - 3:34:06 PM
Last modification on : Saturday, January 27, 2018 - 1:31:25 AM
Document(s) archivé(s) le : Friday, July 10, 2015 - 10:36:01 AM


Version validated by the jury (STAR)


  • HAL Id : tel-01099165, version 2



Ross Hemsley. Probabilistic methods for the analysis of algorithms on random tessellations. Other [cs.OH]. Université Nice Sophia Antipolis, 2014. English. ⟨NNT : 2014NICE4143⟩. ⟨tel-01099165v2⟩



Record views


Files downloads