Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Spreading points evenly in plane

  1. Aug 17, 2010 #1
    Place 6 points in the plane, such that ratio of maximum distance / minimum distance (over these points) is as small as possible. The question is - what is the smallest ratio possible, and can we prove this is a tight bound? The following is my attempt for 6 (and fewer points):

    1) For three points, we can clearly achieve max dist / min dist = 1 (equilateral triangle)

    2) For four points, I tried 2 configurations - a point inside a triangle (couldn't do better than [tex]\sqrt{3}[/tex] doing that though, using an equilateral triangle and it's centroid) . Also, I got a better result with a square (I got [tex]\sqrt{2}[/tex] , with the maximum length side being the diagonal). I think that should be improvable though?

    3) For five points, the best I got was with a regular pentagon (about 1.62).

    4) For six points, a regular hexagon was NOT the best distribution - that gave a ratio of 2 between largest and smallest distance. The best I got was a regular pentagon, with the sixth point at it's intersection of angle bisectors - about a ratio of 1.9. Any way to improve this, and (more trickily) prove it's tight? My source says [tex]\sqrt{3}[/tex] is the tight bound?

    I guess where I'm most stuck is proving a lower bound; i.e, you can't do better than x - I'm not sure how to get started there, even for the n = 4 case. If anyone has ideas or strategies, I'd really appreciate.

    P.S: This isn't a homework or coursework problem - just a random puzzle from Rutgers problem solving seminar website.
     
    Last edited: Aug 17, 2010
  2. jcsd
  3. Aug 20, 2010 #2
    We can use Appolonious circles. Given two points A,B ,moving a third point P such that
    PA/PB is invariant & P is as 'evenly' spaced with respect to other points as possible.
    It follows that the configuration with the minimal no. of different distances is the optimal.
    ( We could keep equalizing the distances reducing the max/min ratio).
     
  4. Dec 7, 2010 #3
    Thank you Eynstone, that was very helpful :).
     
  5. Dec 7, 2010 #4
    What Eynstone said is better, but I'll go ahead and post the idea I had, too. We can place the first two points arbitrarily. Then assigning the value of the max/min ratio to each possible configuration of the remaining n-2 points defines a continuous function from R^(2n-4) to R (almost--you have to either adjoin infinity to the range or exclude configurations with coincident points). Then you might be able to use calculus tools to identify critical points.
     
  6. Dec 7, 2010 #5

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    That function will be continuous but it will not be differentiable everywhere. There will be cusps. Even worse, the optimal configuration will be precisely at a cusp.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook