Kevin Buchin, Technische Universität Eindhoven, Niederlande

Raum Hörsaal B Physikgebäude

11:30 - 12:00 Lehrprobe k-Median Problem

12:00 - 12:45 New Algorithms for Computing Greedy Spanners

Abstract:

Geometric Algorithms play a fundamental role in many application

domains. I will discuss algorithmic challenges in some recent

applications of geometric algorithms in motion planning for industrial

robots, visual analytics, movement ecology, automated cartography, and

the analysis of spatial networks. In particular, motivated by network

analysis, I will present new algorithms for computing the greedy

spanner.

A geometric spanners is a graph on a set of points such that the

distance in the graph approximates the Euclidean distance between the

points. The greedy spanner is a high-quality geometric spanner: its

total weight, edge count and maximal degree are asymptotically optimal

and in practice significantly better than for any other spanner with

reasonable construction time. Unfortunately, all previously known

algorithms that compute the greedy spanner use a quadratic amount of

space, and the largest instances for which the greedy spanner was

computed so far has about 13,000 vertices. I will present a linear-space

algorithm that computes the same spanner in near-quadratic time, which

allows us to compute the spanner on millions of points. Furthermore, I

will present two more approaches to obtain efficient algorithms for

constructing the greedy spanner: The first approach drastically

simplifies our first algorithm. It uses much less space and runs in

near-quadratic time under reasonable assumptions on the input. The

second approach is input-sensitive and aims at subquadratic running

time.