Author |
Topic: Points in the Plane (Read 1364 times) |
|
Barukh
Uberpuzzler
Gender: 
Posts: 2276
|
 |
Points in the Plane
« on: Jul 8th, 2004, 8:43am » |
 Quote  Modify
|
n points are drawn in the plane, and the distances between any pair of points is measured. Find the best bounds for the following parameters of the configuration:
1. The number of different distances.
2. The number of times the minimum distance may occur.
3. The number of times the maximum distance may occur.
4. The number of times any distance may occur.
|
|
 IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Points in the Plane
« Reply #1 on: Jul 8th, 2004, 10:12am » |
Quote Modify
|
1. between 1 and n(n-1)/2
2. between 1 and n(n-1)/2
3. between 1 and n(n-1)/2
4. between 1 and n(n-1)/2
I assume it is OK to have all points in a single spot. For 4. I assume "any distance" refers to the distance between any 2 points.
Now if you don't want any 2 points equal, and "any distance" is any positive real number, all this becomes much more difficult.
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Points in the Plane
« Reply #2 on: Jul 8th, 2004, 11:15am » |
Quote Modify
|
For now:
1. The upper bound is n(n-1)/2. It is obtained with the set {(k,1/k) | k=1,2,...}. Proof: Uniqueness of writing d2 = n + r, with n an integer and r in (0,1).
2. Asymptotically, you can get at least 7/3*n.
3. You can get at least n.
4. Hmmm...
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Points in the Plane
« Reply #4 on: Jul 8th, 2004, 11:35am » |
Quote Modify
|
For 4) I think I can get ~6n. (below)
And yes, 2) is at least ~3n. I don't know why I was thinking so one-dimensionally.
[edit]
Let En be the maximum number of times a single distance can occur with n points. Then En/n is unbounded.
My reasoning is that if we had some layout that gives En = C*n+o(n), then just put down another copy a distance d in an appropriate direction*, giving E2n = (2C+1)*n + o(n), for a ratio of C+1/2.
*Only fintely many don't work, and there are uncountably many to pick from.
This leads me to believe En = Omega(n log n).
[/edit]
[edit]
You can always just do an n-dimensional hypercube with n = 2k vertices and k2k-1 ~ nlog2n/2 edges.
[/edit]
|
| « Last Edit: Jul 8th, 2004, 12:55pm by Eigenray » |
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Points in the Plane
« Reply #5 on: Jul 8th, 2004, 11:39pm » |
Quote Modify
|
1) The number of distinct distances, an upper bound in n(n-1)/2. I will attempt to prove the following (lower bound):
Theorem: Given n = 6t points in a plane, we have at least t+2 distinct distances.
Let the distances taken by the n points be d1 < d2 < d3 < ... < dm (d1 is the minimum distance and dm is the maximum distance)
Let the points be labelled 1,2,3,...,n.
Define the Incidence function for each point k as:
Ik(r) = numbers of points at a distance dr from point k.
where 1 [le] r [le] m and 1 [le] k [le] n (n is the number of points and m is the number of distinct distances)
We will need the following lemma:
Lemma 1: There exists a point k such that 1 [le] Ik(1) [le] 5.
Proof of Lemma 1: Consider the graph G formed as follows. Join point i to j if distance between i and j is d1 (i.e minimum). Get a drawing of G by using the line segment formed by joining point i to j on the plane as an edge of G.
Clearly the degree of point k is Ik(1).
We prove that G is a planar graph, which implies that there is a point of degree [le] 5 and hence there is some k satisfying the condition of Lemma 1.
We prove that the natural drawing of G (using line segment ij as the edge) on the plane has no edges crossing.
Suppose line segment AB crosses line segment CD.
Let AB and CD intersect in E. Now
|AD| < |AE| + |ED| and
|BC| < |BE| + |EC|
adding we get
|AD| + |BC| < |AB| + |CD|
Now |AB| = |CD| = d1. So we get that one of |AD|, |BC| is less than d1. But that it not possible as d1 is the minimum distance.
Hence G is planar, which proves the Lemma.
We will need the following Lemma too.
Lemma 2: Let x be the number of distinct distances formed by 6s points. We can choose no more than R=5s points among those 6s points such that the remaining points have at most x-1 distinct distances. Also, those R points can be chosen such that the shortest distance gets removed.
Proof of Lemma 2:
We use induction on s. s=1 is trivial.
Given 6(s+1) points, by lemma 1, there is point k such that 1 [le] Ik(1) [le] 5. Consider that point and it's 5 neighbours. d1 is the shortest distance. If d1 does not appear in the remaining 6s points we are done. So assume the d1 appears among the remaining 6s points. By induction assumption we can remove no more than R = 5s points and remove the shortest distance. Thus by remove these R points and the 5 neighbours of k, we remove the shortest distance.
By induction on t and applying Lemma 2 we prove the theorem on the lower bound.
|
| « Last Edit: Jul 9th, 2004, 8:12am by Aryabhatta » |
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Points in the Plane
« Reply #6 on: Jul 9th, 2004, 8:25am » |
Quote Modify
|
on Jul 8th, 2004, 11:39pm, Aryabhatta wrote:
Theorem: Given n = 6t points in a plane, we have at least t+2 distinct distances.
|
|
This lower bound, clogn, is way too lax. The current best known lower bound is cn6/7. See the following link:
http://cs.smith.edu/~orourke/TOPP/P39.html
Supposedly there are simple proofs of cn1/2 and cn2/3, as told to me by a friend.
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Points in the Plane
« Reply #7 on: Jul 10th, 2004, 12:51am » |
Quote Modify
|
on Jul 9th, 2004, 8:25am, Aryabhatta wrote:
Hmm… Does that mean this thread is already dead? 
I would still like to see some elementary proofs for, let’s say:
Quote:| Supposedly there are simple proofs of cn1/2 |
|
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Points in the Plane
« Reply #8 on: Jul 10th, 2004, 9:07am » |
Quote Modify
|
on Jul 10th, 2004, 12:51am, Barukh wrote:
Hmm… Does that mean this thread is already dead?
I would still like to see some elementary proofs for cn1/2
|
|
The following for cn1/2 seems too simple. Maybe I am missing something. Anyway, here goes:
Suppose the point P forms r distinct distances (Say d1 to dr) with the other n-1 points. Let nk be the number of points from which P is at a distance dk. (1 [le] k [le] r).
Assume r < n1/2.
Since [sum] nk = n - 1, we must have that there is some s for which ns [ge] n1/2.
Corresponding to this s, these ns points lie on a circle centered at P and radius ds. For any other point Q, at least (ns-1)/2 points of these form distinct distances with Q. (As any two different circles intersect in at most 2 points)
Thus we get the cn1/2 lower bound.
|
| « Last Edit: Jul 10th, 2004, 9:08am by Aryabhatta » |
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Points in the Plane
« Reply #9 on: Jul 11th, 2004, 12:31pm » |
Quote Modify
|
on Jul 8th, 2004, 8:43am, Barukh wrote:n points are drawn in the plane, and the distances between any pair of points is measured. Find the best bounds for the following parameters of the configuration:
1. The number of different distances.
2. The number of times the minimum distance may occur.
3. The number of times the maximum distance may occur.
4. The number of times any distance may occur.
|
|
In what context did this come up? Pretty interesting problem. Interesting enough that lot of research has already been done on it. It would be nice to see a practical application.
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Points in the Plane
« Reply #10 on: Jul 22nd, 2004, 9:06am » |
Quote Modify
|
on Jul 11th, 2004, 12:31pm, Aryabhatta wrote:| In what context did this come up? Pretty interesting problem. Interesting enough that lot of research has already been done on it. It would be nice to see a practical application. |
|
I don’t know. If it was originated by P. Erdos, I doubt it had any practical roots. 
By the way, the cited Erdos’s paper from 1946 proves the following bounds:
1. Minimim [sqrt](n-3/4) – 1/2.
2. Maximum 3n-6.
3. Maximum n.
4. Maximum [sqrt](n3/2) + n/4.
The proofs of all the bounds are elementary. Any takers?
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Points in the Plane
« Reply #11 on: Jul 22nd, 2004, 10:37am » |
Quote Modify
|
on Jul 22nd, 2004, 9:06am, Barukh wrote:
I don’t know. If it was originated by P. Erdos, I doubt it had any practical roots.
By the way, the cited Erdos’s paper from 1946 proves the following bounds:
1. Minimim [sqrt](n-3/4) – 1/2.
2. Maximum 3n-6.
3. Maximum n.
4. Maximum [sqrt](n3/2) + n/4.
The proofs of all the bounds are elementary. Any takers?
|
|
I think the proof O(sqrt[n]) which i gave earlier actually proves 1).
I think this also proves the bound in 4) as to get a bound for 4, consider n(n-1)/2([sqrt](n-3/4) – 1/2)
For 2: (shortest distance)
look at the proof for the 6t points giving rise to t+2 distinct distances which i gave earlier in this thread. In that we prove that the shortest distance graph is planar (with at most n vertices). So number of edges is at most 3n-6.
For 3: (largest distance)
We can show that if AB is the largest distance and CD is the largest distance then line segments AB and CD must intersect. (This follows from sum of diagonals > sum of opposite sides in a quadrilateral). Using this i think we can show that the largest distance graph can have at most one cycle, which gives an upper bound of n.
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Points in the Plane
« Reply #12 on: Jul 22nd, 2004, 12:13pm » |
Quote Modify
|
on Jul 22nd, 2004, 10:37am, Aryabhatta wrote:
I think the proof O(sqrt[n]) which i gave earlier actually proves 1).
|
|
Sorry it doesn't. It only proves half of [sqrt](n-3/4). I need to pay more attention.
|
| « Last Edit: Jul 22nd, 2004, 5:46pm by Aryabhatta » |
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Points in the Plane
« Reply #13 on: Jul 22nd, 2004, 3:05pm » |
Quote Modify
|
If anyone wants to see the 1946 Erdos paper, message me. I'd post a link but it's copyrighted (from JSTOR).
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Points in the Plane
« Reply #14 on: Jul 22nd, 2004, 5:48pm » |
Quote Modify
|
on Jul 22nd, 2004, 10:37am, Aryabhatta wrote:
For 3: (largest distance)
We can show that if AB is the largest distance and CD is the largest distance then line segments AB and CD must intersect. (This follows from sum of diagonals > sum of opposite sides in a quadrilateral). Using this i think we can show that the largest distance graph can have at most one cycle, which gives an upper bound of n.
|
|
Maybe not. I *really* need to pay more attention.
Sorry for the blabber.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print