Title: Imprecision in Computational Geometry

Abstract:
  Given a set of points in the plane, various measures exist that try to
capture certain properties of that point set. Examples of such measures
include the \emph {diameter}: the largest distance between any pair of
points, the \emph {closest pair}: the smallest distance between any pair
of points, the \emph {width}: the smallest distance between two parallel
lines with all points between them, the smallest circle containing all
points, or the smallest axis-aligned bounding box containing all points.
All these measures have been well studied and optimal algorithms to
compute them are known.

  When dealing with real-world data, however, locations of input points
are often not known exactly. If we know for each point that it lies
inside some region, but not where in that region, it becomes interesting
to compute bounds on the possible values of these basic geometric
measures. To make this more precise, we are given a set of regions in
the plane $\script L \subset \script P (\Rn2)$ and a measure $\mu :
\script F (\Rn2) \to \R$ that takes a set of points and gives a real
number, and we want to place one point in each region of $\script L$
such that the resulting point set maximises or minimises $\mu$.