7
$\begingroup$

Definition: The Hausdorff distance is the greatest of all the distances from a point in one set to the closest point in the other set.

Question: Given two convex polygonal regions P1 and P2 on the plane, give an efficient algorithm that locates and orients P2 with respect to P1 (the two regions are allowed to overlap) so that the Hausdorff distance between P1 and P2 is minimized.

$\endgroup$
1
  • 1
    $\begingroup$ Note that an approximation to Hausdorff distance arises from considering pairs of points from one body at maximal distance (a diameter) to a similar pair in the other body. Lining up those diameters may be a good initial step. Gerhard "Maybe Use A Breadth-First Search?" Paseman, 2019.09.01. $\endgroup$ Sep 1, 2019 at 16:00

1 Answer 1

6
$\begingroup$

A polynomial-time algorithm was presented in this paper:

Chew, L. Paul, Michael T. Goodrich, Daniel P. Huttenlocher, Klara Kedem, Jon M. Kleinberg, and Dina Kravets. "Geometric pattern matching under Euclidean motion." Computational Geometry 7, no. 1-2 (1997): 113-124. Elsevier journal link.

If I read their results correctly, "the minimum (bidirectional) Hausdorff problem under Euclidean motion" for polygons can be solved in time $O((m + n)^6 \log^2 mn)$, for polygons of $n$ and $m$ vertices. They did not specialize to convex polygons. These are primarily theoretical results, and I doubt have been implemented. Other work focuses on approximation algorithms, e.g.,

Alt, Helmut, Bernd Behrends, and Johannes Blömer. "Approximate matching of polygonal shapes." Annals of Mathematics and Artificial Intelligence 13, no. 3-4 (1995): 251-265. Springer link.


         
          Fig.5.


A more practical algorithm specialized to convex polygons is described here:

Danilov, Dmitry I., and Aleksei Stanislavovich Lakhtin. "Optimization of the algorithm for determining the Hausdorff distance for convex polygons." Ural Mathematical Journal 4, no. 1 (2018): 14-23. doi.

$\endgroup$
1
  • 1
    $\begingroup$ Dear Professor O'Rourke, Belated thanks for the pointer. $\endgroup$ Sep 12, 2019 at 13:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.