## November 20, Fall Quarter 2009: Thoery Seminar

### 1:00pm in 1423 Bren Hall

#
Preprocessing
Imprecise Points for Efficient Triangulation

## Maarten Loffler, UC Irvine

Traditional algorithms in computational geometry often take a set of
points in the plane as input. An underlying assumption of these algorithms
is that the input points are given precisely. In practice, data is often
collected by imperfect methods and hence imprecise, and the validity of
the output of these algorithms can be questioned. Still, we often have
some information about the imprecision of the points available, such as an
error region around each point.
We investigate what the value of this information is. In this talk, we
show how to preprocess a set of disjoint regions in the plane of total
complexity n in O(n log n) time so that if later one point per set is
specified with precise coordinates, a triangulation of the points can be
computed in linear time. We also show how to compute the Delaunay
triangulation in linear time, but with more restrictions on the shapes of
the regions.