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

Thursday, April 11, 2019

A Distance Set Question

The basic question:
Given nC2 distances, consider the set of all n-point sets on 2D euclidean plane realizing that set of mutual distances. What is the upper bound as a function of n of the number of distinct point sets (point sets unrelated to one another by symmetry transformations; points should be in general position) that realize a given set of nC2 distances?

The last post here (http://nandacumar.blogspot.com/2019/04/3-ellipses-question.html) was part of an attempt to understand the first nontrivial case of the question: n=4. As noted there, for every triangle ABC, we was observed to have a triplet of points {P1,P2,P3} on the boundary of one of the 3-ellipses focused on A,B,C satisfying a set of distance constraints (as described there). This readily gives, for every triangle ABC, 3 distinct 4 point sets -
{P1,A,B,C}, {P2,A,B,C} and {P3,A,B,C}
all of which yield the same distance set of 6 distances. However, I have no proof as yet that 3 is an upper bound for the number of such distance sets for n=4.

Note 1: The same basic question can be asked on other geometries and dimensions.
Note 2: I don't know if given a quadrilateral ABCD, there is some 4-ellipse focused on these 4 points and passing thru a set of 4 points {P1,P2,P3,P4} which have a similar distance property as above. If such a 4-ellipse and quartet of points exist, we have a case of 4 distinct point sets all of which realize the same set of 10 distances.
.......
A further (seemingly simpler) variant of the question:
Find sets of arbitrarily many points in general position such that exactly one point can be moved from its present position to another position without changing the distance set - and such that the two configurations of n points are unrelated by any symmetry.

Experimental Answer: It is observed that for any fixed triangle ABC and a value of the distance sum d that lies in a continuous set of values, we have a pair of points P1 and P2 (not a triplet) such that
distance (P1,A) + distance(P1,B) + distance (P1,C) = d =
distance (P2,A) + distance(P2,B) + distance (P2,C)
and
distance(P1, A) = distance(P2, B)
distance(P1, B) = distance(P2, C)
distance(P1, C) = distance(P2, A).
Note that (as observed in the last post here) a triplet of points {P1,P2,P3} satisfying 3 such sets of distance constraints happen only for one value of d, not a range of values of d.

One further observes that as ABC is held fixed and d is changed continuously, both points P1 and P2 trace curves. This implies that if P1 and P2 are held fixed with ABC allowed to vary, there will be a continuum of triangles of varying sizes and orientations such that for each triangle T among them, P1 and P2 will both yield the same distance sum - of course, if a different triangle T' is taken, the same P1 and P2 will give mutually identical distance sets with this new triangle but with a different distance sum d'. So, to answer the present question, form an arbitrarily large set of points with the vertices of any number of such triangles plus one of P1 or P2. Going from P1 to P2 or vice versa will preserve the distance sum of the large point set.
----------
Update (April 25th 2019):
The 1-D version of the above question is the well-known and still not fully understood 'Turnpike problem'. Even in 2D, there has been progress. The number of 'different' configurations of points realizing a multiset of NC2 distances is known to grow exponentially or thereabouts. For small values of N, exact values have apparently been worked out on a case by case basis. So, the bottom line is that there is not much that someone like me can ask right now! Still, it was fun to observe programmatically (although I can't prove it analytically yet) that for probably for any triangle, there is a 3-ellipse focused at the triangle's vertices that passed thru three points each of which realizes a 4-point set with the vertices that realizes the same set of 6 distances.

Friday, April 05, 2019

3-Ellipses - a Question

Given n points (called foci) in a plane, an n-ellipse is the locus of all points of the plane whose sum of distances to the n foci is a constant d (https://en.wikipedia.org/wiki/N-ellipse). Let me record a simple question on 3-ellipses.

If A, B, C are the foci of a 3-ellipse and d its distance sum, do there exist three points P1, P2, P3 on the boundary of the 3-ellipse such that the following distance relations hold:

P1A = P2B = P3C
P1B = P2C = P3A
P1C = P2A = P3B


If such a triplet of points {P1,P2,P3} necessarily exists on the 3-ellipse for any non-collinear A, B, C and d, how will the triplet {P1,P2,P3} evolve when the 3-ellipse is continuously changed by changing d? What curve does each of P1, P2, P3 trace? Do such triplets have any interesting properties concerning, say, the local curvature of the 3-ellipse?
------
Note: This is known to me... Pairs of points P1,P2 such that: distance(P1,A) = distance(P2,A), distance(P1,B) = distance (P2, C) and distance(P1,C) = distance(P2,B) exist and as d is tuned, both P1 and P2 trace straight lines.
------
Update (April 9th, 2019). Experiments indicate that for any fixed non-collinear point set A,B,C, there is at least one 3-ellipse focused at these 3 points such that a triplet of points {P1,P2,P3} lying on the 3-ellipse satisfies the above set of distance relations. Indications are also that if triangle ABC has no symmetry, there is only one such ellipse for a given {A,B,C} and so there is no non-trivial evolution of the triplet {P1,P2,P3} when A,B,C are held fixed and only the distance sum d is changed.