Some problems on proximity graphs

Tesis doctoral de María Saumell Mendiola

This thesis explores several problems on proximity graphs. The study of proximity graphs is part of a more general area of research, discrete and computational geometry, which is mainly concerned with the study of efficient algorithms to solve problems with some geometric component, as well as their fundamental counterparts. A proximity graph of a set of points in some metric space is a graph where two vertices are adjacent if they satisfy some proximity requirement. we first investigate graph-theoretic properties of certain proximity graphs defined on planar point sets, such as number of edges, vertex-degree, chromatic number, etc. We consider some of the most common proximity graphs of the family of the delaunay graph, in both their standard and higher order versions. Then we concentrate on four classes of higher order proximity graphs and provide lower and upper bounds on their minimum and maximum number of crossings. We also look at the problem of finding the minimum number of layers that are necessary to partition the edges of the graphs so that no two edges of the same layer cross. with the focus still on higher order proximity graphs, we study lower and upper bounds on the number of higher order delaunay triangulations, as well as their expected number for randomly distributed points. We show that arbitrarily large point sets can have a single higher order delaunay triangulation whereas for first order delaunay triangulations, the maximum number is already exponential. Next we show that uniformly distributed points have an expected number of at least 2^(¿_1 n(1+o(1))) first order delaunay triangulations, where ¿_1¿0.525785, and for k>1, the expected number of order-k delaunay triangulations (which are not order-i for any iDatos académicos de la tesis doctoral «Some problems on proximity graphs«

• Título de la tesis:  Some problems on proximity graphs
• Autor:  María Saumell Mendiola
• Universidad:  Politécnica de catalunya
• Fecha de lectura de la tesis:  29/11/2011

Dirección y tribunal

• Director de la tesis
  • Ferran Hurtado Díaz
• Tribunal
  • Presidente del tribunal: rolf Klein
  • david Orden martín (vocal)
  • monique Teillaud (vocal)
  • jean Cardinal (vocal)