[nSLUG] Need an algorithm or heuristic

Gerald Ruderman linux at zdoit.airpost.net
Tue Jul 7 16:47:06 ADT 2015


Vlado,

Thank you for the nice analysis. I suspected it is an NP-hard problem.

The circles are the all the same diameter. I confused matters by
describing the ellipse axes in terms of diameter of the circle.

Gerald

On 7/6/15 6:39, Vlado Keselj wrote:
. . . .
> 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.
> 
. . . .


More information about the nSLUG mailing list