[nSLUG] Need an algorithm or heuristic
linux at zdoit.airpost.net
Tue Jul 7 16:47:06 ADT 2015
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.
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