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.