Return to Answer

I would try to use Voronoi domains $$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 $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{\cdot} \log n)$ --- $O(n{\cdot} \log n)$ a Voronoi diagram see wikipedia and one needs to check check only $O(n)$ points after one makes the diagram.

I would try to use Voronoi domains $$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 $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{\cdot} \log n)$ --- $O(n{\cdot} \log n)$ a Voronoi diagram see wikipedia and one needs to check check only $O(n)$ points after one makes the diagram.

I would try to use Voronoi domains $$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 $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{\cdot} \log n)$ --- $O(n{\cdot} \log n)$ a Voronoi diagram see wikipedia and one needs to check check only $O(n)$ points after one makes the diagram.

I would try to use Voronoi domains $$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 $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{\cdot} \log n)$ --- $O(n{\cdot} \log n)$ a Voronoi diagram see wikipedia and one needs to check check only $O(n)$ points after one makes the diagram.

I would try to use Voronoi domains $$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 $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 and one needs to check check only $O(n)$ points after one makes the diagram.

I would try to use Voronoi domains $$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 $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{\cdot} \log n)$ --- $O(n{\cdot} \log n)$ a Voronoi diagram see wikipedia and one needs to check check only $O(n)$ points after one makes the diagram.