[nSLUG] Need an algorithm or heuristic

Vlado Keselj vlado at dnlp.ca
Mon Jul 6 07:39:07 ADT 2015


Hi,

To add to the previous discussion about the problem:

It is an interesting problem.  In its basic form it is known as Minimum
Geometric Disk Cover: Given a set of points in the plane, find the
minimal number of unit disks to cover the points.

The unit disks (disk is a circle with its interior, unit means r=1), can
be easily replaced with any constant size disks.  This problem is NP-hard,
which means that it would be very hard (practically impossible) to find an
efficient solution to find the minimal number of disks.  However, there
are ideas about how to approach it to find an approximate number of
minimal disks.   Some ideas are discussed at this URL for example:

http://stackoverflow.com/questions/15882202/minimum-number-of-circles-with-radius-r-to-cover-n-points

There are many variations discussed in literature; for example, allowing
circles of various diameters, but the cost is not only number of circles
but it is a function of those diameters (or radii).  This has applications
in cell-phone coverage by cell-phone towers.  Another variation is that
centers of disks cannot be arbitrary but must be at certain points, and
then it becomes closer to the classical set cover problem, which is also
NP-hard BTW.

I wonder why you use circles of two different sizes.  If the goal is to
find the minimal number of circles in the cover, then you would always use
larger circles since the smaller ones do not offer any advantage.

The fact that the points are closely arranged at a shape of an ellipse can
actually be quite helpful.  It seems to me that in that special case it is
possible to come up with an efficient optimal solution using dynamic
programming technique.

Interestingly, at the Preliminary Atlantic ACM programming competition in
2013 I proposed a somewhat similar problem under the name "Oil
Exploration".   The problem asked for optimal disk cover for a set of
points on a long rectangular grid of 4 x n dimension.  This problem has an
efficient dynamic programming based solution.  The same idea could be used
on points on a ellipsoid band, but it may not be so easy to adapt.


Regards,
Vlado

On Sun, 5 Jul 2015, Oliver Doepner wrote:

> I guess what I suggested will result in a so-called "greedy algorithm".
> https://en.wikipedia.org/wiki/Greedy_algorithm
>
> On Sun, Jul 5, 2015 at 11:54 AM, Gerald Ruderman <linux at zdoit.airpost.net> wrote:
>       Oliver,
>
>       Good next step for me.
>
>       Evan,
>
>       Thanks for telling me what it is called. Now I can do some research.
>
>       Gerald
>
>       On 7/4/15 19:00, Evan Lowry wrote:
>       > Sounds like a geometric variation of maximum
>       > coverage: https://en.wikipedia.org/wiki/Maximum_coverage_problem
>       >
>       > Might serve as a starting point.
>       >
>       > On Sat, Jul 4, 2015 at 6:46 PM, Gerald Ruderman <linux at zdoit.airpost.net
>       > <mailto: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 <mailto:nSLUG at nslug.ns.ca>
>       >     http://nslug.ns.ca/mailman/listinfo/nslug
>       >
>       >
>       >
>       >
>       > --
>       > Evan Lowry
>       > www.exitiumonline.com
>       > <http://www.exitiumonline.com> | https://github.com/Lykathia
>       >
>       >
>       > _______________________________________________
>       > nSLUG mailing list
>       > nSLUG at nslug.ns.ca
>       > http://nslug.ns.ca/mailman/listinfo/nslug
>       >
>       _______________________________________________
>       nSLUG mailing list
>       nSLUG at nslug.ns.ca
>       http://nslug.ns.ca/mailman/listinfo/nslug
>
>
>
>
> --
> Oliver Doepner
> http://oliver.doepner.net/
>
>


More information about the nSLUG mailing list