Wolfgang Mulzer, FU Berlin

Raum SR006

9:00 - 9:30 Lehrprobe k-Median Problem

9:30 - 10:15 New Perspectives on Old Problems

 

Abstract:

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