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$ – David Richerby Oct 31 '14 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 '14 at 18:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.