# Location Information

#### Thu, May 23, 2019 12:30 CEST

######
**Speakers:**
Maarten Löffler

######
**Tags:**
Computational Geometry, Delaunay Triangulations, Voronoi Diagrams, Well-Separated Pair Decomposition, Quadtrees

Let P be a set of n points in the plane. In the traditional geometric algorithms view, P is given as an unordered sequence of locations (usually pairs of x and y coordinates). There are many interesting and useful structures that one can build on top of P: the Delaunay triangulation, Voronoi diagram, well-separated pair decomposition, quadtree, etc. These structures can all be represented in O(n) space but take Omega(n log n) time to construct on a Real RAM, and, hence, contain information about P that is encoded in P but cannot be directly read from P.

In this talk I will explore the question how much information about the
structure of a set of points can be derived from their locations, especially
when we are *uncertain* about the locations of the points.

### Bio

Maarten Löffler is currently an assistant professor at Utrecht University. He has been a post-doc researcher at the Bren School of information and computer sciences of the University of California, Irvine. He was a PhD-student at Utrecht University.

The speaker is hosted by the Algorithms Group.