TECH-MUSINGS

Thoughts On Algorithms, Geometry etc...

Thursday, April 25, 2019

Hausdorff distances and Convexity

I recently came to know about Hausdorff distances from a presentation by Prof. Janos Pach:

Hausdorff Distance: Informally, two sets are close in the Hausdorff distance if every point of either set is close to some point of the other set. The Hausdorff distance is the longest distance you can be forced to travel by an adversary who chooses a point in one of the two sets, from where you then must travel to the other set. (Wiki)

Questions:
Among all 2D convex regions with fixed area and perimeter, which two are maximal Hausdorff distance apart?
The question can be repeated in other dimensions and for parameters other than area + perimeter.

Further, one can ask: if a convex region is convex fair partitioned (spicy chicken theorem), can something can be claimed about the range of Hausdorff distances among the pieces getting minimized - say "the partition that minimizes the range of hausdorff distances is one of the many possible convex equal area partitions"?

Note 1: While measuring hausdorff distances between a pair of pieces, we are allowed to apply any isometry to one piece so that its Hausdorff distance from the other piece is minimized. How to position two convex polygonal regions so that the hausdorff distance between them is minimized must be a well-studied problem.
Note 2: The motivation for this question is the known fact that among all triangulations with a given set of points, the Delauay triangulation yields the 'fattest' triangles.
Note 3: Is the partition of any convex region into N pieces at the least Hausdorff distance from each other guaranteed to yield convex pieces? This page has a possible counter example due to Erich Friedman: https://arxiv.org/ftp/arxiv/papers/1002/1002.0122.pdf

Some more Questions :

1. Find two convex regions A and B of which A is of unit area and perimeter such that (1) A and B are the highest possible Hausdorff distance apart and (2) both the highest possible number of copies of A that can be arranged kissing a single B and the highest possible number of copies of B that can be arranged kissing a single A are equal. This question has natural analogs in higher dimensions.
2. One can also ask, without bringing in Hausdorff: Find convex A and B such that both have the same area and perimeter but with the number of A units that can kiss a single B and the number of B units that can kiss a single A are as different as possible.
Guess: The pair {right triangle, ellipse} seems promising as an answer to this question - and perhaps as the pair maximally apart in terms of Hausdorff distance.

Update (12th September 2019): Here are some pointers to be added to the above comment: "How to position two convex polygonal regions so that the hausdorff distance between them is minimized must be a well-studied problem":
https://mathoverflow.net/questions/339621/to-minimize-the-hausdorff-distance-between-convex-polygonal-regions/339637#339637

0 Comments:

Post a Comment

<< Home