[nSLUG] Need an algorithm or heuristic

Johann Tienhaara jtienhaara at yahoo.com
Wed Jul 8 13:37:56 ADT 2015


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>
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
>

  
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://nslug.ns.ca/pipermail/nslug/attachments/20150708/0ac160df/attachment.html>


More information about the nSLUG mailing list