## Preprocessing Imprecise Points and Splitting Triangulations

Traditional algorithms in computational geometry assume that the input points are given precisely. In practice, data is usually imprecise, but information about the imprecision is often available. In this context, we investigate what the value of this information is. We show here how to preprocess a set of disjoint regions in the plane of total complexity n in O(n log n) time so that if one point per set is specified with precise coordinates, a triangulation of the points can be computed in linear time. In our solution, we solve another problem which we believe to be of independent interest. Given a triangulation with red and blue vertices, we show how to compute a triangulation of only the blue vertices in linear time.

keywords: Computational Geometry, Data Structures, Data Imprecision

### Journal Article (peer-reviewed)

Joseph Mitchell, Maarten Löffler, Marc van Kreveld

Preprocessing Imprecise Points and Splitting Triangulations

SIAM Journal on Computing

39, 7, 2990–3000, 2010

### Conference Proceedings (peer-reviewed)

Joseph Mitchell, Maarten Löffler, Marc van Kreveld

Preprocessing Imprecise Points and Splitting Triangulations

Proc. 19th International Symposium on Algorithms and Computation

LNCS 5369, 544–555, 2008

### Technical Report (not reviewed)

Joseph Mitchell, Maarten Löffler, Marc van Kreveld

Preprocessing Imprecise Points and Splitting Triangulations

UU-CS-2009-007, 2009

back to list