Geometric Spanner Networks
Joachim Gudmundsson (University of Sydney)
NICTA SML SEMINARDATE: 2012-07-12
TIME: 11:15:00 - 12:00:00
LOCATION: NICTA - 7 London Circuit
CONTACT: JavaScript must be enabled to display this email address.
ABSTRACT:
Consider a set S of n points in d-dimensional Euclidean space. A network on S can be modelled as an undirected graph G with vertex set S of size n and an edge set E where every edge (u,v) has a weight. A geometric (Euclidean) network is a network where the weight of the edge (u,v) is the Euclidean distance between its endpoints. Given a real number t > 1 we say that G is a t-spanner for S, if for each pair of points u,v in S, there exists a path in G of weight at most t times the Euclidean distance between u and v.
In this talk we give an overview of the area of geometric spanners
including the most common construction algorithms to obtain
spanners of linear size.
BIO:
