HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

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 :
Complete list of metadata

Cited literature [114 references]  Display  Hide  Download

Contributor : Abes Star :  Contact
Submitted on : Thursday, April 9, 2015 - 3:34:06 PM
Last modification on : Saturday, May 1, 2021 - 3:41:30 AM
Long-term archiving on: : 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