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$.

**P.S.** I deleted my answer earlier sinse I miscalculated time; I thought it takes forever. But Alexander Griffing noticed that, it is $O(n \log n)$ --- $O(n \log n)$ a Voronoi diagram
[see wikipedia][3]
and one needs to check check only $O(n)$ points after one makes the diagram.  


  [1]: http://en.wikipedia.org/wiki/Voronoi_diagram
  [2]: http://en.wikipedia.org/wiki/Power_of_a_point
  [3]: http://en.wikipedia.org/wiki/Fortune%2527s_algorithm