everyone.
I'm looking for paper with proof of NP-completeness following, or similar problem.
Given:
- Area $S \subset \mathbb{N}^2$, let it be convex or rectangular, I believe it doesn't matter
- Maximum possible radius $R_{max}$
Required:
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.