Wolfgang Mulzer, FU Berlin
9:00 - 9:30 Lehrprobe k-Median Problem
9:30 - 10:15 New Perspectives on Old Problems
I will discuss two classic problems from computational geometry and
present new perspectives on them.
First, I will talk about nearest neighbor searching in high dimensions.
Given a set of points in high dimensions, we would like to construct a
data structure for nearest neighbor queries: for a given query point q,
find the point closest to q. Since all known exact data structures for
this problem deteriorate exponentially with the dimension, approximate
solutions are of primary interest. Approximate nearest neighbor search
has been studied extensively, and many interesting solutions are known.
I will show how to extend this problem to the case that the query
objects are arbitrary k-flats. We will see that also in this case
reasonable bounds are still possible.
Second, I will consider the problem of finding the Voronoi diagram of a
planar point set. Voronoi diagrams have a rich and long history, and
they are ubiquitous in computational geometry. Optimal algorithms for
computing them have been known for a long time. I will consider the
space-efficient setting, where the input resides in read-only memory and
a sublinear amount of additional workspace is available. In this case,
we can obtain a trade-off between space and running time that is almost
optimal. Our approach combines simulated parallelism with a
space-efficient random sampling strategy.
Based on joint work with M. Korman, H.L. Nguyen, A. van Renssen, M.
Roeloffzen, P. Seiferth, and Y. Stein