## Existence and Computation of Tours through Imprecise Points

Assume that an ordered set of imprecise points is given, where each point is specified by a region in which the point may lie. This set determines an imprecise polygon. We show that it is NP-hard to decide whether it is possible to place the points inside their regions in such a way that the resulting polygon is simple. Furthermore, it is NP-hard to minimize the length of a simple tour visiting the regions in order, when the connections between consecutive regions do not need to be straight line segments. We also present two linear-time algorithms to compute the shortest and longest possible tour for the case where the polygon is not required to be simple and the regions are squares.

keywords: Computational Geometry, Data Imprecision

### Journal Article (peer-reviewed)

Maarten Löffler

Existence and Computation of Tours through Imprecise Points

International Journal of Computational Geometry and Applications

21, 1, 1–24, 2011

### Workshop or Poster (weakly reviewed)

Maarten Löffler

Existence of Simple Tours of Imprecise Points

Proc. 23rd European Workshop on Computational Geometry

22–25, 2007

### Technical Report (not reviewed)

Maarten Löffler

Existence of Simple Tours of Imprecise Points

UU-CS-2007-003, 2007

back to list