Events
10
October
2024
10.
10.
2024
11
October
2024
11.
10.
2024
14
October
2024
14.
10.
2024
25
October
2024
25.
10.
2024
31
October
2024
31.
10.
2024

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