[nSLUG] Need an algorithm or heuristic

Gerald Ruderman linux at zdoit.airpost.net
Wed Jul 8 18:02:31 ADT 2015


Johann,

A quick reading of your well reasoned suggestion makes me think it is a
good solution. This morning I was doing some rough calculations of how
long it would take a computer to find an optimal solution trying every
possible set of circles.

This is similar to the problem of locating cell phone base stations.
They have the added limitation that only some locations are available
for base stations. Much work has been done on that. Now that I know what
it is called, thanks to this list, I may be able to use some that of
research.

This problem will come up now and then for me. Sometimes it will be
small sets, sometimes much larger than the 200 or so I have to deal with
now. Any solution, including third-party software is acceptable. Also
re-examining the data looking for ways to not have to cover as many points.

Gerald

On 7/8/15 12:37, Johann Tienhaara wrote:
> I have not done any due diligence on this suggestion, and my math might
> be wrong, and this might be way too approximate for your needs, so take
> this all with a big grain of salt...
> 
> A simple brute force approximation comes to mind.  Since there are only
> 200 points, create a 200 x 200 table (40,000 cells) with the distances
> between points, plus one extra column.  For each row, tally up the count
> of points whose distances are less than the common radius of the small
> circles.  Put the count of "inside the circle" neighbours for that row
> into the right column.  Search for the highest count (tie resolution is
> arbitrary since this algorithm is only approximate anyway).  Place a
> circle on the point identified by that row.  Then zero out all columns
> that are touched by that circle (distance <= radius).  Again find the
> highest "inside the circle" neighbours count.  Repeat ad nauseam until
> the table is full of zeros.
> 
> The idea is to centre the circles on points that have a lot of close-by
> neighbours.  This algorithm could fail horribly depending on the data
> set (for example where all points are 1.01 * radius apart, and 100
> circles placed halfway between pairs of points would be a much better
> solution than what the algorithm would generate, i.e. 200 circles).
> 
> 
> A trivial example data set, with 7 points, and the small circles all
> have radius=1.0:
> 
> Point 1 (0.0, 0.5)
> Point 2 (0.5, 0.3)
> Point 3 (1.0, 0.0)
> Point 4 (1.4, 0.3)
> Point 5 (2.0, 0.5)
> Point 6 (1.7, 0.8)
> Point 7 (0.8, 0.7)
> 
>     1   2   3   4   5   6   7     #
>    --- --- --- --- --- --- ---   ---
> 1  0.0 0.6 1.2 1.5 2.0 1.8 0.9    3
> 2  0.6 0.0 0.6 0.9 1.6 1.3 0.5    5
> 3  1.2 0.6 0.0 0.5 1.2 1.1 0.8    4
> 4  1.5 0.9 0.5 0.0 0.7 0.6 0.8    6 <- Highest count
> 5  2.0 1.6 1.2 0.6 0.0 0.5 1.3    3
> 6  1.8 1.3 1.1 0.6 0.5 0.0 1.0    4
> 7  0.9 0.5 0.8 0.8 1.3 1.0 0.0    6
> 
> So we'll put a circle centred at point # 4.
> 
> Zero'd out:
> 
>     1   2   3   4   5   6   7     #
>    --- --- --- --- --- --- ---   ---
> 1  0.0 0.0 0.0 0.0 0.0 0.0 0.0    7 <- Highest count
> 2  0.6 0.0 0.0 0.0 0.0 0.0 0.0    7
> 3  1.2 0.0 0.0 0.0 0.0 0.0 0.0    6
> 4  1.5 0.0 0.0 0.0 0.0 0.0 0.0    6
> 5  2.0 0.0 0.0 0.0 0.0 0.0 0.0    6
> 6  1.8 0.0 0.0 0.0 0.0 0.0 0.0    6
> 7  0.9 0.0 0.0 0.0 0.0 0.0 0.0    7
> 
> Our next circle will be centred at point # 1.
> 
> Zero'd out:
> 
>     1   2   3   4   5   6   7     #
>    --- --- --- --- --- --- ---   ---
> 1  0.0 0.0 0.0 0.0 0.0 0.0 0.0    7
> 2  0.0 0.0 0.0 0.0 0.0 0.0 0.0    7
> 3  0.0 0.0 0.0 0.0 0.0 0.0 0.0    7
> 4  0.0 0.0 0.0 0.0 0.0 0.0 0.0    7
> 5  0.0 0.0 0.0 0.0 0.0 0.0 0.0    7
> 6  0.0 0.0 0.0 0.0 0.0 0.0 0.0    7
> 7  0.0 0.0 0.0 0.0 0.0 0.0 0.0    7
> 
> Now the table is full of zeros, so we're done.
> 
> In this trivial example the answer we come up with is a minimum number
> of circles is 2, and they could be centred on points # 1 and 4.
> 
> In fact we can tell by inspecting the data that placing a single circle
> at (1.0, 0.5) would be the optimal solution.  But of course this
> algorithm would never even look at that region of space.  Which reduces
> the search space immensely, but also eliminates a few (typically very
> few) optimal or near-optimal circle positions.
> 
> 
> Sorry for any bad math, algorithm oversights, etc.
> 
> 
> Out of curiosity is this a one-time task?  Or does it need to be run on
> different data sets over time?  Do you have to program it, or could you
> use third party software to just come up with a solution (like a max sat
> solver or something along those lines)?
> 
> Let us know how it turns out!  Sounds like an intriguing project.
> 
> 
> Incidentally this topic reminds me of a solution to a more or less
> unrelated problem.  It was in a paper in a comp sci graphics journal
> maybe 16 or 17 years ago, proposing using "bounding spheres" to make
> collision detection quick and easy.  2 spheres s1 and s2 collide if they
> are located less than radius1 + radius2 distance apart.  The concept is
> brilliant, but the challenge is covering the space occupied by an
> arbitrarily-shaped 3-dimensional object with a "reasonable" (i.e.
> minimal or close to minimal) number of spheres.  I wish I knew what to
> look up or where, because it was a well-written, thought-provoking
> article, and might have even provided some other angles of attack for
> this problem.
> 
> Johann
> 
> 
> 
> 
> 
> On Sat, Jul 4, 2015 at 6:46 PM, Gerald Ruderman <linux at zdoit.airpost.net <http://nslug.ns.ca/mailman/listinfo/nslug>>
> wrote:
> 
>>/Hi, />//>/A little off topic: />//>/I need an algorithm or heuristic to solve this problem: />//>/There are 200 points in 2 space. Plotted they form approximately an />/ellipse. I have circles of fixed size whose diameter is about 1/40 of />/the long dimension of the ellipse and about 1/20 of the smaller axis. I />/need to cover all the points in this space with the minimum number of />/circles. The ideal solution is not required something that is close is />/needed. />//>/I have played around with this for a few weeks and am stumped. If a />/search were phrased correctly I might find an algorithm to code, but I />/don't know what to search for. />//>/Seeking help either with where to look or a similar problem or a solution. />//>/Thanks />//>/-- />/Gerald />/_______________________________________________ />/nSLUG mailing list />/nSLUG at nslug.ns.ca <http://nslug.ns.ca/mailman/listinfo/nslug> />/http://nslug.ns.ca/mailman/listinfo/nslug />
> 
> 
> 
> _______________________________________________
> nSLUG mailing list
> nSLUG at nslug.ns.ca
> http://nslug.ns.ca/mailman/listinfo/nslug
> 


More information about the nSLUG mailing list