Title: |
Paired Pointset Traversal |

Authors: |
Peter Hui, Marcus Schaefer |

Abstract: |
In the Paired Pointset Traversal problem we ask whether, given twosets A = {a _{1}, ..., a_{n}}
and B = {b_{1}, ..., b_{n}}
in the plane, there is an ordering pi of the points
such that both a_{pi(1)},
..., a_{pi(n)}
and b_{pi(1)},
..., b_{pi(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: |
[ps] |