Lynx Roundup, January 7th 2022

Lynx Roundup, January 7th 2022

Robot Rebel News

Matthew Alhonte
Matthew Alhonte

Hausdorff distance measures how far two subsets of a metric space are from each other. Informally, it is the greatest of all distances from a point in one set to the closest point in the other set. Two sets are “close” if for any one point on either set, the nearest point in the other set is “not too far”. (See reference 2 for more details on the intuition behind Hausdorff distance.)

Formally, if X and Y are two non-empty subsets of a metric space with distance metric d, then their Hausdorff distance d_H (X, Y) is defined to be

\begin{aligned} d_H (X, Y) = \max \left\{ \sup_{x \in X} \inf_{y \in Y} d(x, y), \sup_{y \in Y} \inf_{x \in X} d(x, y) \right\}. \end{aligned}

The two terms within the \max need not be the same: the figure below (taken from Wikipedia) shows this for a particular example.

Computing the Hausdorff distance between the green line X and the blue line Y. (Credit: Wikipedia.)

There are some algorithms for computing Hausdorff distance in certain cases. For example, reference 3 gives a linear time algorithm for Hausdorff distances between two convex polygons, while reference 4 gives an algorithm for computing it between two parametric curves in \mathbb{R}^n.

Hausdorff distance is commonly used in computer vision, where you are given an image and you want to map that image to a template, or model that you have. More details on its use can be found through a quick search on google scholar.

References:

  1. Wikipedia. Hausdorff distance.
  2. Grégoire, N., and Bouillot, M. Hausdorff distance between convex polygons.
  3. Atallah, M. J. (1983). A linear time algorithm for the Hausdorff distance between convex polygons.
  4. Kim, I.-S., and McLean, W. (2013). Computing the Hausdorff distance between two sets of parametric curves.
Productivity and the Workweek - shorter hours
Research | Emma Frejinger
Bizarre subatomic “quasiparticle” reproduces like a living cell
“In order to integrate skyrmions into future devices, science must have an accurate understanding of their formation mechanism.”
Animals that can do math understand more language than we think
Some animals demonstrate an ability for mathematics that reflects a more sophisticated understanding of language.
In defense of blub studies
Why it’s worth it to deeply understand the fiddly, boring-seeming details of the computer systems you use every day.
Roundup

Matthew Alhonte

Supervillain in somebody's action hero movie. Experienced a radioactive freak accident at a young age which rendered him part-snake and strangely adept at Python.