I would try to use [Voronoi domains][1] 
$$V_i=\{\\,x\in\mathbb R^2\mid |o_i-x|\le |o_j-x|^2\ \text{for all}\ j\\,\},$$
where $o_i$ is the center of $C_i$.
I guess there are some algorithms which produce it.
Then you only need to check that

 - each vertexes $a\in C_{n+1}$ of Voronoi domain $V_i$.
 - and each point of intersection $\partial V_i\cap \partial C_{n+1}$

lies in $C_i$.

In the case of varying radii, you can still use modified Voronoi domains;
$$V_i=\{\\,x\in\mathbb R^2\mid f_i(x)\le f_j(x)\ \text{for all}\ j\\,\}.$$
where $f_i(x)$ is the [power of the point][2] $x$ with respect to $C_i$.


  [1]: http://en.wikipedia.org/wiki/Voronoi_diagram
  [2]: http://en.wikipedia.org/wiki/Power_of_a_point