I have an arbitrary 2d area on the xy plane. I want to cover it with N discs such that all points in the area have at least one disc overlapping it. A disc with center (xc, yc) placed inside this area has a radius r that is a function of (xc,yc).

I am looking for references or algorithms that can help me to minimize N and generate the disc coordinates. So far the papers I've turned up on the discrete unit disk covering (DUDC) problem assume equally sized discs.

Luckily, for my particular application, r = f(x,y) is somewhat insensitive to changes in x and y. The heuristic I've been using is to use a modified hexagonal packing, but I would love to explore different approaches.

If anyone has any papers or online references that I could consult, I'd really appreciate it! I am not a computer scientist so if this is covered in a good textbook, I'd also be open to purchasing that.

I would be extra happy if it also discussed ways of minimizing N by allowing some degree of uncovered space, and also did a treatment on using ellipsoids instead of uniform radius discs.

  • $\begingroup$ This seems too vague to answer. It seems very unlikely that somebody has considered the problem you ask in full generality, i.e., the radius is an arbitrary function of $x$ and $y$. It sounds like this would be a research problem, if you said what $f$ was; doubly so if you wanted approximations and ellipsoids. $\endgroup$ Oct 31, 2014 at 23:26
  • $\begingroup$ Thanks. I was afraid this might be the case. I might stick with generic annealing methods or a hex packing. $\endgroup$
    – krapht
    Nov 1, 2014 at 18:32


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.