Title:	Paired Pointset Traversal
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 in general. This has consequences for the complexity of computing the Fréchet distance of two-dimensional surfaces. We also investiage tractable variants and approximation results.
Full Paper:	[ps]