Title: Paired Pointset Traversal
Published: March 2004
Authors: Peter Hui, Marcus Schaefer
Abstract: In the Paired Pointset Traversal problem we ask whether, given two
sets A = {a1, ..., an} and B = {b1, ..., bn} in the plane, there is an ordering pi of the points such that both api(1), ..., api(n) and bpi(1), ..., bpi(n) are self-avoiding polygonal arcs? We show that Paired Pointset Traversal is NP-complete. This has consequences for the complexity of computing the Fréchet distance of two-dimensional surfaces.
Full Paper: [postscript]