I'm looking for paper with proof of NP-completeness following, or similar problem.


  1. Area $S \subset \mathbb{N}^2$, let it be convex or rectangular, I believe it doesn't matter
  2. Maximum possible radius $R_{max}$


Find a minimal possible set $C$ of pairs $(v, r)$, where $v$ is circle center and $r$ is circle radius, which would represent a circles completely covering given rectangle $S$.

Circles may overlap.

My particular problem is that I need to proof NP-completeness my own problem (landscape coverage with geodesic network stations) and I'm looking for similar problem proofs as example. I heard that NP-completeness of "Circle coverage problem" is well-known, but I have hard times finding it in the Internet.

For reference, my problem is about covering arbitrary area (non-polygonal, with voids inside) with circles pair-intersection and additional requirements for circles position to each other (each circle must be included into at least two other circles). As I need to find NP-complete problem to reduce it to my problem, I may forget about non-polygonal space, but I can't ignore additional position constraints and pair-intersections, so I can't just reduce circles coverage problem to my own.

I'm currently looking at Set Cover Problem and I wonder if topic problem is just geometric interpretation of this "set cover problem" given a set $U$ of all area inner and border points and family $\mathcal{F}$ of all "circular" subsets as in $\{\,(x, y) \mid x^2 + y^2 \leqslant R_{max}\,\}$, but I'm not sure if I correctly understand wikipedia article.

  • $\begingroup$ Must all of the circles be entirely contained within the area? In other words, is it okay for a circle to have parts outside of the area as long as the center is within the area? If that is okay, then I think your problem has a linear time solution: Simply cover your area with a lattice of circles with centers equally spaced $\sqrt{2R_{max}^2}$ apart from each other. $\endgroup$ – ESultanik Mar 23 '13 at 19:59

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.