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 algorithms. 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.