Abstract:

Thinking about data structures in an information theoretic way has
led to a beautiful understanding of many problems, with matching
upper and lower bounds. A simple example, hashing, tells us that to
search for an exact copy of a query item in a set of N items, we
only need O(lgN) bits of information about the query, regardless of
the domain. A more complicated example, fusion trees, tells us that
only b bits of information allow us to search for predecessors
among b^{Omega(1)} numbers, each having b bits of precision.

Unfortunately, low-dimensional computational geometry has usually
not been studied from this perspective, for two main reasons: (1)
computational geometry has typically been stuck in a continuous
setting, with input having arbitrary precision; (2) more
importantly, there has been no convincing result regarding problems
of a nonorthogonal nature.

With regard to (1), I will argue that moving computational geometry
into the discrete realm is unavoidable, if we want to stay
connected to practice. As for (2), I will try to demonstrate that
moving computational geometry into the discrete realm is quite
interesting, by describing a few compelling recent results for
nonorthogonal problems such as point location, construction of
Voronoi diagrams and dynamic convex hulls.

Parts based on joint work with Timothy Chan and Erik Demaine, and
on a paper appearing in FOCS'06.