TECH-MUSINGS

Thoughts On Algorithms, Geometry etc...

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.

0 Comments:

Post a Comment

<< Home