Smallest Set Containing All n-point Sets

  • Thread starter jgm340
  • Start date
  • #1
104
2
I've been thinking about this. Suppose you have an n-point set P in Rm which has the property that for any two points x, y in P, ||x - y|| < 2. If we fix n, what can we say about the smallest set S in Rm that contains P, allowing for both translations and orthogonal transformations of S?

If we start in R2, the answer is not what you'd expect! As illustrated in this picture, P must be able to fit inside of any 2 by 2 square after only translation:
attachment.php?attachmentid=26839&stc=1&d=1278316407.png

That is, if I were to have a square hoola-hoop, I could swing it around P. However, for n > 2, the intersection of all those squares would not necessarily fit inside a circle of diameter 2.

For n=2, the smallest set would be something like [0,1] U {2}.
For n=3, I think the smallest set would be {x = (x1, x2) : ||x - (0,1)|| < 2, x1 < 0, x2 < 0} U {x = (x2,x2) : x1 = 0, -1 < x2 < 1}

Any thoughts?
 

Attachments

  • shape rotated.png
    shape rotated.png
    1.7 KB · Views: 502

Answers and Replies

  • #2
radou
Homework Helper
3,120
6
I'm not sure what exactly you mean by "translations" and "orthogonal transformation".

If you have an n-point subset P of R^m, take max{||x - y||, x, y from P} = diam(P) = r = d(x0, y0) (for some x0, y0 in P), and then the closed ball B(x0, r) around x with radius r contains the set P.
 
  • #3
104
2
I'm not sure what exactly you mean by "translations" and "orthogonal transformation".

If you have an n-point subset P of R^m, take max{||x - y||, x, y from P} = diam(P) = r = d(x0, y0) (for some x0, y0 in P), and then the closed ball B(x0, r) around x with radius r contains the set P.

Yes, but that's not the smallest. :wink:
Take the intersection of the balls about x0 and y0. This would also necessarily contain P.

About the "translations and orthogonal transformations" business: I'm looking for a closed form for a set S which must "be able to contain" P. By "be able to contain", I mean that for any P, we ought to find some transformation T (involving only rotations, reflections, and translations) such that P is contained in T(S).
 

Related Threads on Smallest Set Containing All n-point Sets

Replies
2
Views
3K
  • Last Post
Replies
5
Views
2K
  • Last Post
Replies
8
Views
5K
  • Last Post
Replies
7
Views
4K
  • Last Post
Replies
6
Views
9K
  • Last Post
Replies
7
Views
10K
  • Last Post
Replies
4
Views
2K
  • Last Post
Replies
2
Views
3K
  • Last Post
Replies
5
Views
3K
Top