Results 1 to 6 of 6

Math Help - Maximum circle enclosing 12 points

  1. #1
    Newbie
    Joined
    Feb 2008
    Posts
    3

    Maximum circle enclosing 12 points

    I have been posed a problem in class which asks me to find an algorithm that finds a circle that encloses at most 12 points on a grid 2000.00 by 2000.00, no matter where the circle is centered, given a random set of points. I can't think of the first thing to try here. Please someone help.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by circleBounding View Post
    I have been posed a problem in class which asks me to find an algorithm that finds a circle that encloses at most 12 points on a grid 2000.00 by 2000.00, no matter where the circle is centered, given a random set of points. I can't think of the first thing to try here. Please someone help.
    how many random points are we talking here?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by circleBounding View Post
    I have been posed a problem in class which asks me to find an algorithm that finds a circle that encloses at most 12 points on a grid 2000.00 by 2000.00, no matter where the circle is centered, given a random set of points. I can't think of the first thing to try here. Please someone help.
    Is this a circle of the same radius, but arbitary centre?

    If the radius can be different depending on the centre try this (all units are
    in grid pitch units):


    Code:
    centre=(a,b)
    
    Rlo=0.5
    Rhi=2000.0
    
    If point at (a,b)
       Nlo=1
    Else
       Nlo=0
    Endif
    Nhi = total number points (assumed >12)
    
    Repeat
    {
      Rwrk=(Rhi+Rlo)/2
      Nwrk=number of points enclosed by circle centred at (a,b) of radius Rwrk
      If Nwrk==12 
        break
      Endif
      If Nwrk>=12
        Rhi=Rwrk
      Else If Nwrk<12
        Rlo=Rwrk
      Endif
    }
    
    Return Rwrk
    RonL
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Feb 2008
    Posts
    3
    The number of points is random, as well as their position.

    Thanks for the algorithm Captain, but it is arbitary center point, same radius at all points as far as i can tell.

    Here is the actual question:

    Background: Something about breeding toads in the "Paranta Forest".

    "Given the positions of the female toads in the Paranta forest, and assuming that no male toads have yet been released, work out the largest territory for a male toad that, no matter where you put it, will not enclose more than 12 females. A toads territory can be generalised to a circle centered on that toad."
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by circleBounding View Post
    The number of points is random, as well as their position.

    Thanks for the algorithm Captain, but it is arbitary center point, same radius at all points as far as i can tell.

    Here is the actual question:

    Background: Something about breeding toads in the "Paranta Forest".

    "Given the positions of the female toads in the Paranta forest, and assuming that no male toads have yet been released, work out the largest territory for a male toad that, no matter where you put it, will not enclose more than 12 females. A toads territory can be generalised to a circle centered on that toad."
    2000x2000 is a small number of grid points for a modern computer, so brute force should solve this.

    Loop over grid points

    calculate the distance to 13 closest females

    end loop

    required radius is anyting less than the mininmum of the distances just calculated.

    You may have to do some pre-sorting of the females positions to make the
    calculation practical.

    Even if this won't execute in a reasonable time, the question does not seem to ask that the algorithm be practical

    RonL
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Feb 2008
    Posts
    3
    problem is, it is in float accuracy, so it is actually 200,000*200,000 distinct points. Also, in the class I'm doing, efficiency is key, so the algorithm has to run very quickly
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Minimum and Maximum points
    Posted in the Calculus Forum
    Replies: 1
    Last Post: May 17th 2011, 06:53 AM
  2. Replies: 4
    Last Post: May 2nd 2010, 03:34 PM
  3. Replies: 7
    Last Post: March 15th 2010, 04:10 PM
  4. Replies: 3
    Last Post: July 28th 2009, 10:28 AM
  5. Enclosing a Rectangualr Field
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: October 7th 2005, 10:34 AM

Search Tags


/mathhelpforum @mathhelpforum