wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> Points in the Plane
        
(Message started by: Barukh on Jul 8^th, 2004, 8:43am)

Title: Points in the Plane
Post by Barukh on Jul 8^th, 2004, 8:43am

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.

Title: Re: Points in the Plane
Post by Grimbal on Jul 8^th, 2004, 10:12am

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.

Title: Re: Points in the Plane
Post by Eigenray on Jul 8^th, 2004, 11:15am

For now:
1. The upper bound is [hide]n(n-1)/2[/hide]. It is obtained with the set [hide]{(k,1/k) | k=1,2,...}[/hide]. Proof: [hide]Uniqueness of writing d² = n + r, with n an integer and r in (0,1)[/hide].

2. Asymptotically, you can get at least [hide]7/3*n[/hide].

3. You can get at least [hide]n[/hide].

4. Hmmm...

Title: Re: Points in the Plane
Post by towr on Jul 8^th, 2004, 11:29am

I think for 2 I can get [hide]3n[/hide] asymptotically..

Title: Re: Points in the Plane
Post by Eigenray on Jul 8^th, 2004, 11:35am

~~For 4) I think I can get ~[hide]6n[/hide].~~ (below)
And yes, 2) is at least ~[hide]3n[/hide]. I don't know why I was thinking so one-dimensionally.

[edit]
Let E_n be the maximum number of times a single distance can occur with n points. Then E_n/n [hide]is unbounded[/hide].
My reasoning is that [hide]if we had some layout that gives E_n = C*n+o(n), then just put down another copy a distance d in an appropriate direction*, giving E_2n = (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 E_n = Omega(n log n)[/hide].
[/edit]

[edit]
You can always just do [hide]an n-dimensional hypercube with n = 2^k vertices and k2^k-1 ~ nlog₂n/2 edges[/hide].
[/edit]

Title: Re: Points in the Plane
Post by Aryabhatta on Jul 8^th, 2004, 11:39pm

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 = 6^t points in a plane, we have at least t+2 distinct distances.

Let the distances taken by the n points be d₁ < d₂ < d₃ < ... < d_m (d₁ is the minimum distance and d_m is the maximum distance)

Let the points be labelled 1,2,3,...,n.

Define the Incidence function for each point k as:

I_k(r) = numbers of points at a distance d_r 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] I_k(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 d₁ (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 I_k(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| = d₁. So we get that one of |AD|, |BC| is less than d₁. But that it not possible as d₁ 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] I_k(1) [le] 5. Consider that point and it's 5 neighbours. d₁ is the shortest distance. If d₁ does not appear in the remaining 6s points we are done. So assume the d₁ 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.

Title: Re: Points in the Plane
Post by Aryabhatta on Jul 9^th, 2004, 8:25am

on 07/08/04 at 23:39:31, Aryabhatta wrote:

Theorem: Given n = 6^t 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 cn^6/7. See the following link:
http://cs.smith.edu/~orourke/TOPP/P39.html

Supposedly there are simple proofs of cn^1/2 and cn^2/3, as told to me by a friend.

Title: Re: Points in the Plane
Post by Barukh on Jul 10^th, 2004, 12:51am

on 07/09/04 at 08:25:35, Aryabhatta wrote:

See the following link: http://cs.smith.edu/~orourke/TOPP/P39.html

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 cn^1/2

Title: Re: Points in the Plane
Post by Aryabhatta on Jul 10^th, 2004, 9:07am

on 07/10/04 at 00:51:10, Barukh wrote:

Hmm… Does that mean this thread is already dead? :-/

I would still like to see some elementary proofs for cn^1/2

The following for cn^1/2 seems too simple. Maybe I am missing something. Anyway, here goes:

Suppose the point P forms r distinct distances (Say d₁ to d_r) with the other n-1 points. Let n_k be the number of points from which P is at a distance d_k. (1 [le] k [le] r).

Assume r < n^1/2.
Since [sum] n_k = n - 1, we must have that there is some s for which n_s [ge] n^1/2.

Corresponding to this s, these n_s points lie on a circle centered at P and radius d_s. For any other point Q, at least (n_s-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 cn^1/2 lower bound.

Title: Re: Points in the Plane
Post by Aryabhatta on Jul 11^th, 2004, 12:31pm

on 07/08/04 at 08:43:32, Barukh 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.

Title: Re: Points in the Plane
Post by Barukh on Jul 22^nd, 2004, 9:06am

on 07/11/04 at 12:31:20, 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. ;D

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](n³/2) + n/4.

The proofs of all the bounds are elementary. Any takers?

Title: Re: Points in the Plane
Post by Aryabhatta on Jul 22^nd, 2004, 10:37am

on 07/22/04 at 09:06:27, Barukh wrote:

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 6^t 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.

Title: Re: Points in the Plane
Post by Aryabhatta on Jul 22^nd, 2004, 12:13pm

on 07/22/04 at 10:37:43, 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.

Title: Re: Points in the Plane
Post by Eigenray on Jul 22^nd, 2004, 3:05pm

If anyone wants to see the 1946 Erdos paper, message me. I'd post a link but it's copyrighted (from JSTOR).

Title: Re: Points in the Plane
Post by Aryabhatta on Jul 22^nd, 2004, 5:48pm

on 07/22/04 at 10:37:43, 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.