Polygon Containment and Translational Min-Hausdorff-Distance between
Segment Sets are 3sum-Hard
and Sariel Har-Peled.
The 3sum problem represents a class of problems conjectured
to require Vmega(n2) time to solve, where n
is the size of the input. Given two polygons P and Q
in the plane, we show that some variants of the decision problem,
whether there exists a transformation of P that makes
it contained in Q, are 3sum-hard. In the first variant
P and Q are any simple polygons and the allowed
transformations are translations only; in the second and third
variants both polygons are convex and we allow either rotations
only or any rigid motion. We also show that finding the translation
in the plane that minimizes the Hausdorff distance between two
segment sets is 3sum-hard.