Some new results on proximity graphs
Staff - Faculty of Informatics
Start date: 23 May 2011
End date: 24 May 2011
The Faculty of Informatics is pleased to announce a seminar given by Maria Saumell
DATE: Monday, May 23rd, 2011
PLACE: USI Università della Svizzera italiana, room SI-004, Black building (Via G. Buffi 13)
TIME: 11.30
ABSTRACT:
A proximity graph on a set of vertices that represent points or other objects in some metric space is a graph that attempts to describe the relations of proximity of that set of vertices. In a proximity graph two vertices are connected if they are close to each other under some criteria, and this makes them useful in several areas such as pattern recognition, computer graphics, terrain representation, or mesh generation. In the talk I will review the main results on proximity graphs developed in my thesis. This includes bounds on combinatorial and geometric properties (number of edges, minimum and maximum degree, number of crossings) of some higher order proximity graphs. I will also present bounds on the number of higher order Delaunay triangulations that a point set can have, as well as some results on shortest paths in the Delaunay triangulation. Finally, I will make some fast remarks on the Delaunay triangulation with respect to the $L_{\infty}$ metric, and I will describe a generalization of proximity graphs consisting of defining them on a given weighted graph.
BIO:
Maria Saumell is a PhD student at Universitat Politècnica de Catalunya in Barcelona (Spain). She received her Master's degree in Applied Mathematics at the same university in 2008. Her research interests are in Combinatorial and Computational Geometry, with a focus on the study of proximity graphs in the plane.
HOST: Prof. Evanthia Papadopoulou
