ICS Theory Group

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.