Simply Realising an Imprecise Polyline is NP-hard

Thijs van der Horst, Tim Ophelders, Bart van der Steenhoven

We consider the problem of deciding, given a sequence of regions, if there is a choice of points, one for each region, such that the induced polyline is simple or weakly simple, me…