[talks] W Mulzer preFPO

Melissa Lawson mml at CS.Princeton.EDU
Mon Oct 5 11:16:29 EDT 2009

Wolfgang Mulzer will present his preFPO on Thursday October 8 at 10:30 AM in Room 402.  
The members of his committee are:  Bernard Chazelle, advisor; David Dobkin and Bob 
Tarjan, readers; Sanjeev Arora and Boaz Barak, nonreaders.  Everyone is invited to attend 
his talk.  His abstract follows below.

Low-Entropy Computational Geometry

The worst-case model for algorithm design does not always reflect the
real world:  inputs may have additional structure to be exploited, and
sometimes data can be imprecise or become available only gradually. To
better understand these situations, we examine several scenarios where
additional information can affect the design and analysis of geometric

First, we consider hereditary convex hulls: given a three-dimensional
convex polytope and a two-coloring of its vertices, we can find the
individual monochromatic polytopes in linear expected time. This can be
generalized in many ways, eg, to more than two colors, and to the
offline-problem where we wish to preprocess a polytope so that any
large-enough subpolytope can be found quickly.

Next, we assume that the point coordinates have a bounded number of
bits, and that we can do standard bit manipulations in constant time.
Then Delaunay triangulations can be found in expected time O(n(log log
n)^(1/2)). Our result is based on a new connection between quadtrees and
Delaunay triangulations, which also lets us generalize a recent result
by Loeffler and Snoeyink about Delaunay triangulations for imprecise points.

Finally, we consider randomized incremental constructions when the input
permutation is generated by a bounded-degree Markov chain, and show that
the resulting running time is almost optimal for chains with a constant
eigenvalue gap.

More information about the talks mailing list