Events
06
October
2022
06.
10.
2022
07
October
2022
07.
10.
2022
13
October
2022
13.
10.
2022
20
October
2022
20.
10.
2022
27
October
2022
27.
10.
2022
03
November
2022
03.
11.
2022
10
November
2022
10.
11.
2022

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