Mixing
How to find the smallest enclosing circle over a set of circles?
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
I have a set of circles on a plane, each defined by their X, Y and R parameters. I need to find the smallest enclosing circle over all of them. Essentially, this is a variation of this question, except my circles can have different radii. What would be a fast (linear time) algorithm of doing that?
I'm posting it here instead of StackOverflow/programmers.se because I think this is a predominantly math problem, rather than programming. Please correct me if I'm wrong.
My math is OK-ish, but I'm struggling to come up with a good solution. The best I've come up with is to replace each circle with 8 points, and then calculate the SEC for those with the help of Welzl's algorithm. It will not be exact, but should be an acceptable approximation for my purposes. However I wonder if there is a better and more precise algorithm?
geometry circle
edited Apr 13 '17 at 12:20
Community♦
1
asked Sep 19 '16 at 14:14
Vilx-
1085
add a comment |Â
up vote
1
down vote
favorite
I have a set of circles on a plane, each defined by their X, Y and R parameters. I need to find the smallest enclosing circle over all of them. Essentially, this is a variation of this question, except my circles can have different radii. What would be a fast (linear time) algorithm of doing that?
I'm posting it here instead of StackOverflow/programmers.se because I think this is a predominantly math problem, rather than programming. Please correct me if I'm wrong.
My math is OK-ish, but I'm struggling to come up with a good solution. The best I've come up with is to replace each circle with 8 points, and then calculate the SEC for those with the help of Welzl's algorithm. It will not be exact, but should be an acceptable approximation for my purposes. However I wonder if there is a better and more precise algorithm?
geometry circle
edited Apr 13 '17 at 12:20
Community♦
1
asked Sep 19 '16 at 14:14
Vilx-
1085
Hint: The smallest enclosing circle of a set of points can be found in time O(N Log(N)) using the farthest-point Voronoi diagram. I wouldn't be surprised that this can be generalized to circles of different radii using a weighted Voronoi.
– Yves Daoust
Sep 20 '16 at 7:06
@Vilx- This inf.ethz.ch/personal/emo/DoctThesisFiles/fischer05.pdf is a paper that might help you.
– MNKY
Sep 23 '16 at 13:19
@Vilx- This is a package of an algorithm that solves your problem: people.inf.ethz.ch/gaertner/subdir/software/miniball.html
– MNKY
Sep 23 '16 at 14:29
add a comment |Â
up vote
1
down vote
favorite
up vote
1
down vote
favorite
I have a set of circles on a plane, each defined by their X, Y and R parameters. I need to find the smallest enclosing circle over all of them. Essentially, this is a variation of this question, except my circles can have different radii. What would be a fast (linear time) algorithm of doing that?
I'm posting it here instead of StackOverflow/programmers.se because I think this is a predominantly math problem, rather than programming. Please correct me if I'm wrong.
My math is OK-ish, but I'm struggling to come up with a good solution. The best I've come up with is to replace each circle with 8 points, and then calculate the SEC for those with the help of Welzl's algorithm. It will not be exact, but should be an acceptable approximation for my purposes. However I wonder if there is a better and more precise algorithm?
geometry circle
edited Apr 13 '17 at 12:20
Community♦
1
asked Sep 19 '16 at 14:14
Vilx-
1085
I have a set of circles on a plane, each defined by their X, Y and R parameters. I need to find the smallest enclosing circle over all of them. Essentially, this is a variation of this question, except my circles can have different radii. What would be a fast (linear time) algorithm of doing that?
I'm posting it here instead of StackOverflow/programmers.se because I think this is a predominantly math problem, rather than programming. Please correct me if I'm wrong.
My math is OK-ish, but I'm struggling to come up with a good solution. The best I've come up with is to replace each circle with 8 points, and then calculate the SEC for those with the help of Welzl's algorithm. It will not be exact, but should be an acceptable approximation for my purposes. However I wonder if there is a better and more precise algorithm?
geometry circle
edited Apr 13 '17 at 12:20
Community♦
1
asked Sep 19 '16 at 14:14
Vilx-
1085
edited Apr 13 '17 at 12:20
Community♦
1
edited Apr 13 '17 at 12:20
Community♦
1
edited Apr 13 '17 at 12:20
Community♦
1
1
asked Sep 19 '16 at 14:14
Vilx-
1085
asked Sep 19 '16 at 14:14
Vilx-
1085
asked Sep 19 '16 at 14:14
Vilx-
1085
1085
Hint: The smallest enclosing circle of a set of points can be found in time O(N Log(N)) using the farthest-point Voronoi diagram. I wouldn't be surprised that this can be generalized to circles of different radii using a weighted Voronoi.
– Yves Daoust
Sep 20 '16 at 7:06
@Vilx- This inf.ethz.ch/personal/emo/DoctThesisFiles/fischer05.pdf is a paper that might help you.
– MNKY
Sep 23 '16 at 13:19
@Vilx- This is a package of an algorithm that solves your problem: people.inf.ethz.ch/gaertner/subdir/software/miniball.html
– MNKY
Sep 23 '16 at 14:29
add a comment |Â
Hint: The smallest enclosing circle of a set of points can be found in time O(N Log(N)) using the farthest-point Voronoi diagram. I wouldn't be surprised that this can be generalized to circles of different radii using a weighted Voronoi.
– Yves Daoust
Sep 20 '16 at 7:06
@Vilx- This inf.ethz.ch/personal/emo/DoctThesisFiles/fischer05.pdf is a paper that might help you.
– MNKY
Sep 23 '16 at 13:19
@Vilx- This is a package of an algorithm that solves your problem: people.inf.ethz.ch/gaertner/subdir/software/miniball.html
– MNKY
Sep 23 '16 at 14:29
Hint: The smallest enclosing circle of a set of points can be found in time O(N Log(N)) using the farthest-point Voronoi diagram. I wouldn't be surprised that this can be generalized to circles of different radii using a weighted Voronoi.
– Yves Daoust
Sep 20 '16 at 7:06
Hint: The smallest enclosing circle of a set of points can be found in time O(N Log(N)) using the farthest-point Voronoi diagram. I wouldn't be surprised that this can be generalized to circles of different radii using a weighted Voronoi.
– Yves Daoust
Sep 20 '16 at 7:06
@Vilx- This inf.ethz.ch/personal/emo/DoctThesisFiles/fischer05.pdf is a paper that might help you.
– MNKY
Sep 23 '16 at 13:19
@Vilx- This inf.ethz.ch/personal/emo/DoctThesisFiles/fischer05.pdf is a paper that might help you.
– MNKY
Sep 23 '16 at 13:19
@Vilx- This is a package of an algorithm that solves your problem: people.inf.ethz.ch/gaertner/subdir/software/miniball.html
– MNKY
Sep 23 '16 at 14:29
@Vilx- This is a package of an algorithm that solves your problem: people.inf.ethz.ch/gaertner/subdir/software/miniball.html
– MNKY
Sep 23 '16 at 14:29
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
2
down vote
accepted
Real solution:
B. Gärter from ETH zurich has come up with this C++ package embodying the algorithm to solve the problem. Even in higher dimensions. https://people.inf.ethz.ch/gaertner/subdir/software/miniball.html
more info here: https://www.inf.ethz.ch/personal/emo/DoctThesisFiles/fischer05.pdf
I leave my previous answers below so people can see how primitive they are.
Approximation involving center of mass of the points:
Let $c(x_i,y_i,r_i)$ define a circle with position $(x_i,y_i)$ and radius $r_i$
Let $(x_c,y_c) = (sum_i=1^nx_i/n :,sum_i=1^ny_i/n) :::::$ be the center of of mass of the $n$ circle positions.
Next our concern is finding the smallest radius $r_c$ that encloses the circles from the center of mass.
This is done by finding the maximum value of the distance from the center $(x_c,y_c)$ to the circle center positions $(x_i,y_i)$ plus their radius $r_i$:
$r_c = max (sqrt(x_c - x_j,y_c-y_j) cdot (x_c - x_j,y_c -y_j)+r_j)$
We now have a circle $C(x_c,y_c,r_c)$ enclosing the other circles. This is not the optimal circle but the algorithm to find it is linearly bounded, $o(n)$.
Approximation involving the smallest enclosing rectangle for the circles
This is a basic approach that finds the enclosing rectangle defined by its boundaries.
We obtain $Rect(x_min, x_max, y_min, y_max)$ that defines the boundaries of an axis oriented rectangle. Where:
$x_min = min( :x_j - r_j)$
$x_max = max( :x_j + r_j)$
$y_min = min( :y_j - r_j)$
$y_max = max( :y_j + r_j)$
Now the center of our enclosing circle is $(x_c,y_c ) = ((x_min+ x_max)/2:, (y_min + y_max)/2)$
We obtain the radius as before:
$r_c = max (sqrt(x_c - x_j,y_c-y_j) cdot (x_c - x_j,y_c -y_j)+r_j)$
We now have a circle $C(x_c,y_c,r_c)$ enclosing the other circles. This is not the optimal circle but the algorithm to find it is linearly bounded, $o(n)$. Its a start I hope someone posts an exact solution. Its an interesting problem.
answered Sep 20 '16 at 14:05
MNKY
331410
This is the first idea that came to my mind, but I quickly discarded it. Consider the scenario where there are 101 circles, all with the same radius. 100 of them are closely clustered, while the last one is a fair deal further from the rest. The center of the mass will be somewhere inside the crowd, while the outlying circle will make the radius way, way bigger than necessary.
– Vilx-
Sep 20 '16 at 14:58
@Vilx- Why are you trying to get the solution to this problem? What is the domain You are bringing it from? It looks nontrivial. A more suitable solution could be arrived at by making the circle smaller and sliding it in the direction of the max position until you hit a second circle.
– MNKY
Sep 20 '16 at 21:22
@Vilx- another possible approximate solution is to find the smallest enclosing rectangle for our circles and use its center as the center of the enclosing circle. It's basic but it's cheap computationally.
– MNKY
Sep 21 '16 at 0:22
@igael : I was not thinking of rotating rectangles, just axis oriented ones, I edited the sol to explain what I mean.
– MNKY
Sep 21 '16 at 5:27
I need this for a force-directed graph layout algorithm, and the problem there is pretty much exactly this. I need to group a bunches of nodes (circular) and calculate forces between these groups, taking the size (visual, not count or weight) of the group into account, so that the groups don't overlap.
– Vilx-
Sep 21 '16 at 7:10
 |Â
show 5 more comments
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
2
down vote
accepted
Real solution:
B. Gärter from ETH zurich has come up with this C++ package embodying the algorithm to solve the problem. Even in higher dimensions. https://people.inf.ethz.ch/gaertner/subdir/software/miniball.html
more info here: https://www.inf.ethz.ch/personal/emo/DoctThesisFiles/fischer05.pdf
I leave my previous answers below so people can see how primitive they are.
Approximation involving center of mass of the points:
Let $c(x_i,y_i,r_i)$ define a circle with position $(x_i,y_i)$ and radius $r_i$
Let $(x_c,y_c) = (sum_i=1^nx_i/n :,sum_i=1^ny_i/n) :::::$ be the center of of mass of the $n$ circle positions.
Next our concern is finding the smallest radius $r_c$ that encloses the circles from the center of mass.
This is done by finding the maximum value of the distance from the center $(x_c,y_c)$ to the circle center positions $(x_i,y_i)$ plus their radius $r_i$:
$r_c = max (sqrt(x_c - x_j,y_c-y_j) cdot (x_c - x_j,y_c -y_j)+r_j)$
We now have a circle $C(x_c,y_c,r_c)$ enclosing the other circles. This is not the optimal circle but the algorithm to find it is linearly bounded, $o(n)$.
Approximation involving the smallest enclosing rectangle for the circles
This is a basic approach that finds the enclosing rectangle defined by its boundaries.
We obtain $Rect(x_min, x_max, y_min, y_max)$ that defines the boundaries of an axis oriented rectangle. Where:
$x_min = min( :x_j - r_j)$
$x_max = max( :x_j + r_j)$
$y_min = min( :y_j - r_j)$
$y_max = max( :y_j + r_j)$
Now the center of our enclosing circle is $(x_c,y_c ) = ((x_min+ x_max)/2:, (y_min + y_max)/2)$
We obtain the radius as before:
$r_c = max (sqrt(x_c - x_j,y_c-y_j) cdot (x_c - x_j,y_c -y_j)+r_j)$
We now have a circle $C(x_c,y_c,r_c)$ enclosing the other circles. This is not the optimal circle but the algorithm to find it is linearly bounded, $o(n)$. Its a start I hope someone posts an exact solution. Its an interesting problem.
answered Sep 20 '16 at 14:05
MNKY
331410
This is the first idea that came to my mind, but I quickly discarded it. Consider the scenario where there are 101 circles, all with the same radius. 100 of them are closely clustered, while the last one is a fair deal further from the rest. The center of the mass will be somewhere inside the crowd, while the outlying circle will make the radius way, way bigger than necessary.
– Vilx-
Sep 20 '16 at 14:58
@Vilx- Why are you trying to get the solution to this problem? What is the domain You are bringing it from? It looks nontrivial. A more suitable solution could be arrived at by making the circle smaller and sliding it in the direction of the max position until you hit a second circle.
– MNKY
Sep 20 '16 at 21:22
@Vilx- another possible approximate solution is to find the smallest enclosing rectangle for our circles and use its center as the center of the enclosing circle. It's basic but it's cheap computationally.
– MNKY
Sep 21 '16 at 0:22
@igael : I was not thinking of rotating rectangles, just axis oriented ones, I edited the sol to explain what I mean.
– MNKY
Sep 21 '16 at 5:27
I need this for a force-directed graph layout algorithm, and the problem there is pretty much exactly this. I need to group a bunches of nodes (circular) and calculate forces between these groups, taking the size (visual, not count or weight) of the group into account, so that the groups don't overlap.
– Vilx-
Sep 21 '16 at 7:10
 |Â
show 5 more comments
up vote
2
down vote
accepted
Real solution:
B. Gärter from ETH zurich has come up with this C++ package embodying the algorithm to solve the problem. Even in higher dimensions. https://people.inf.ethz.ch/gaertner/subdir/software/miniball.html
more info here: https://www.inf.ethz.ch/personal/emo/DoctThesisFiles/fischer05.pdf
I leave my previous answers below so people can see how primitive they are.
Approximation involving center of mass of the points:
Let $c(x_i,y_i,r_i)$ define a circle with position $(x_i,y_i)$ and radius $r_i$
Let $(x_c,y_c) = (sum_i=1^nx_i/n :,sum_i=1^ny_i/n) :::::$ be the center of of mass of the $n$ circle positions.
Next our concern is finding the smallest radius $r_c$ that encloses the circles from the center of mass.
This is done by finding the maximum value of the distance from the center $(x_c,y_c)$ to the circle center positions $(x_i,y_i)$ plus their radius $r_i$:
$r_c = max (sqrt(x_c - x_j,y_c-y_j) cdot (x_c - x_j,y_c -y_j)+r_j)$
We now have a circle $C(x_c,y_c,r_c)$ enclosing the other circles. This is not the optimal circle but the algorithm to find it is linearly bounded, $o(n)$.
Approximation involving the smallest enclosing rectangle for the circles
This is a basic approach that finds the enclosing rectangle defined by its boundaries.
We obtain $Rect(x_min, x_max, y_min, y_max)$ that defines the boundaries of an axis oriented rectangle. Where:
$x_min = min( :x_j - r_j)$
$x_max = max( :x_j + r_j)$
$y_min = min( :y_j - r_j)$
$y_max = max( :y_j + r_j)$
Now the center of our enclosing circle is $(x_c,y_c ) = ((x_min+ x_max)/2:, (y_min + y_max)/2)$
We obtain the radius as before:
$r_c = max (sqrt(x_c - x_j,y_c-y_j) cdot (x_c - x_j,y_c -y_j)+r_j)$
We now have a circle $C(x_c,y_c,r_c)$ enclosing the other circles. This is not the optimal circle but the algorithm to find it is linearly bounded, $o(n)$. Its a start I hope someone posts an exact solution. Its an interesting problem.
answered Sep 20 '16 at 14:05
MNKY
331410
This is the first idea that came to my mind, but I quickly discarded it. Consider the scenario where there are 101 circles, all with the same radius. 100 of them are closely clustered, while the last one is a fair deal further from the rest. The center of the mass will be somewhere inside the crowd, while the outlying circle will make the radius way, way bigger than necessary.
– Vilx-
Sep 20 '16 at 14:58
@Vilx- Why are you trying to get the solution to this problem? What is the domain You are bringing it from? It looks nontrivial. A more suitable solution could be arrived at by making the circle smaller and sliding it in the direction of the max position until you hit a second circle.
– MNKY
Sep 20 '16 at 21:22
@Vilx- another possible approximate solution is to find the smallest enclosing rectangle for our circles and use its center as the center of the enclosing circle. It's basic but it's cheap computationally.
– MNKY
Sep 21 '16 at 0:22
@igael : I was not thinking of rotating rectangles, just axis oriented ones, I edited the sol to explain what I mean.
– MNKY
Sep 21 '16 at 5:27
I need this for a force-directed graph layout algorithm, and the problem there is pretty much exactly this. I need to group a bunches of nodes (circular) and calculate forces between these groups, taking the size (visual, not count or weight) of the group into account, so that the groups don't overlap.
– Vilx-
Sep 21 '16 at 7:10
 |Â
show 5 more comments
up vote
2
down vote
accepted
up vote
2
down vote
accepted
Real solution:
B. Gärter from ETH zurich has come up with this C++ package embodying the algorithm to solve the problem. Even in higher dimensions. https://people.inf.ethz.ch/gaertner/subdir/software/miniball.html
more info here: https://www.inf.ethz.ch/personal/emo/DoctThesisFiles/fischer05.pdf
I leave my previous answers below so people can see how primitive they are.
Approximation involving center of mass of the points:
Let $c(x_i,y_i,r_i)$ define a circle with position $(x_i,y_i)$ and radius $r_i$
Let $(x_c,y_c) = (sum_i=1^nx_i/n :,sum_i=1^ny_i/n) :::::$ be the center of of mass of the $n$ circle positions.
Next our concern is finding the smallest radius $r_c$ that encloses the circles from the center of mass.
This is done by finding the maximum value of the distance from the center $(x_c,y_c)$ to the circle center positions $(x_i,y_i)$ plus their radius $r_i$:
$r_c = max (sqrt(x_c - x_j,y_c-y_j) cdot (x_c - x_j,y_c -y_j)+r_j)$
We now have a circle $C(x_c,y_c,r_c)$ enclosing the other circles. This is not the optimal circle but the algorithm to find it is linearly bounded, $o(n)$.
Approximation involving the smallest enclosing rectangle for the circles
This is a basic approach that finds the enclosing rectangle defined by its boundaries.
We obtain $Rect(x_min, x_max, y_min, y_max)$ that defines the boundaries of an axis oriented rectangle. Where:
$x_min = min( :x_j - r_j)$
$x_max = max( :x_j + r_j)$
$y_min = min( :y_j - r_j)$
$y_max = max( :y_j + r_j)$
Now the center of our enclosing circle is $(x_c,y_c ) = ((x_min+ x_max)/2:, (y_min + y_max)/2)$
We obtain the radius as before:
$r_c = max (sqrt(x_c - x_j,y_c-y_j) cdot (x_c - x_j,y_c -y_j)+r_j)$
We now have a circle $C(x_c,y_c,r_c)$ enclosing the other circles. This is not the optimal circle but the algorithm to find it is linearly bounded, $o(n)$. Its a start I hope someone posts an exact solution. Its an interesting problem.
answered Sep 20 '16 at 14:05
MNKY
331410
Real solution:
B. Gärter from ETH zurich has come up with this C++ package embodying the algorithm to solve the problem. Even in higher dimensions. https://people.inf.ethz.ch/gaertner/subdir/software/miniball.html
more info here: https://www.inf.ethz.ch/personal/emo/DoctThesisFiles/fischer05.pdf
I leave my previous answers below so people can see how primitive they are.
Approximation involving center of mass of the points:
Let $c(x_i,y_i,r_i)$ define a circle with position $(x_i,y_i)$ and radius $r_i$
Let $(x_c,y_c) = (sum_i=1^nx_i/n :,sum_i=1^ny_i/n) :::::$ be the center of of mass of the $n$ circle positions.
Next our concern is finding the smallest radius $r_c$ that encloses the circles from the center of mass.
This is done by finding the maximum value of the distance from the center $(x_c,y_c)$ to the circle center positions $(x_i,y_i)$ plus their radius $r_i$:
$r_c = max (sqrt(x_c - x_j,y_c-y_j) cdot (x_c - x_j,y_c -y_j)+r_j)$
We now have a circle $C(x_c,y_c,r_c)$ enclosing the other circles. This is not the optimal circle but the algorithm to find it is linearly bounded, $o(n)$.
Approximation involving the smallest enclosing rectangle for the circles
This is a basic approach that finds the enclosing rectangle defined by its boundaries.
We obtain $Rect(x_min, x_max, y_min, y_max)$ that defines the boundaries of an axis oriented rectangle. Where:
$x_min = min( :x_j - r_j)$
$x_max = max( :x_j + r_j)$
$y_min = min( :y_j - r_j)$
$y_max = max( :y_j + r_j)$
Now the center of our enclosing circle is $(x_c,y_c ) = ((x_min+ x_max)/2:, (y_min + y_max)/2)$
We obtain the radius as before:
$r_c = max (sqrt(x_c - x_j,y_c-y_j) cdot (x_c - x_j,y_c -y_j)+r_j)$
We now have a circle $C(x_c,y_c,r_c)$ enclosing the other circles. This is not the optimal circle but the algorithm to find it is linearly bounded, $o(n)$. Its a start I hope someone posts an exact solution. Its an interesting problem.
answered Sep 20 '16 at 14:05
MNKY
331410
edited Sep 23 '16 at 15:04
answered Sep 20 '16 at 14:05
MNKY
331410
answered Sep 20 '16 at 14:05
MNKY
331410
answered Sep 20 '16 at 14:05
MNKY
331410
331410
This is the first idea that came to my mind, but I quickly discarded it. Consider the scenario where there are 101 circles, all with the same radius. 100 of them are closely clustered, while the last one is a fair deal further from the rest. The center of the mass will be somewhere inside the crowd, while the outlying circle will make the radius way, way bigger than necessary.
– Vilx-
Sep 20 '16 at 14:58
@Vilx- Why are you trying to get the solution to this problem? What is the domain You are bringing it from? It looks nontrivial. A more suitable solution could be arrived at by making the circle smaller and sliding it in the direction of the max position until you hit a second circle.
– MNKY
Sep 20 '16 at 21:22
@Vilx- another possible approximate solution is to find the smallest enclosing rectangle for our circles and use its center as the center of the enclosing circle. It's basic but it's cheap computationally.
– MNKY
Sep 21 '16 at 0:22
@igael : I was not thinking of rotating rectangles, just axis oriented ones, I edited the sol to explain what I mean.
– MNKY
Sep 21 '16 at 5:27
I need this for a force-directed graph layout algorithm, and the problem there is pretty much exactly this. I need to group a bunches of nodes (circular) and calculate forces between these groups, taking the size (visual, not count or weight) of the group into account, so that the groups don't overlap.
– Vilx-
Sep 21 '16 at 7:10
 |Â
show 5 more comments
This is the first idea that came to my mind, but I quickly discarded it. Consider the scenario where there are 101 circles, all with the same radius. 100 of them are closely clustered, while the last one is a fair deal further from the rest. The center of the mass will be somewhere inside the crowd, while the outlying circle will make the radius way, way bigger than necessary.
– Vilx-
Sep 20 '16 at 14:58
@Vilx- Why are you trying to get the solution to this problem? What is the domain You are bringing it from? It looks nontrivial. A more suitable solution could be arrived at by making the circle smaller and sliding it in the direction of the max position until you hit a second circle.
– MNKY
Sep 20 '16 at 21:22
@Vilx- another possible approximate solution is to find the smallest enclosing rectangle for our circles and use its center as the center of the enclosing circle. It's basic but it's cheap computationally.
– MNKY
Sep 21 '16 at 0:22
@igael : I was not thinking of rotating rectangles, just axis oriented ones, I edited the sol to explain what I mean.
– MNKY
Sep 21 '16 at 5:27
I need this for a force-directed graph layout algorithm, and the problem there is pretty much exactly this. I need to group a bunches of nodes (circular) and calculate forces between these groups, taking the size (visual, not count or weight) of the group into account, so that the groups don't overlap.
– Vilx-
Sep 21 '16 at 7:10
This is the first idea that came to my mind, but I quickly discarded it. Consider the scenario where there are 101 circles, all with the same radius. 100 of them are closely clustered, while the last one is a fair deal further from the rest. The center of the mass will be somewhere inside the crowd, while the outlying circle will make the radius way, way bigger than necessary.
– Vilx-
Sep 20 '16 at 14:58
This is the first idea that came to my mind, but I quickly discarded it. Consider the scenario where there are 101 circles, all with the same radius. 100 of them are closely clustered, while the last one is a fair deal further from the rest. The center of the mass will be somewhere inside the crowd, while the outlying circle will make the radius way, way bigger than necessary.
– Vilx-
Sep 20 '16 at 14:58
@Vilx- Why are you trying to get the solution to this problem? What is the domain You are bringing it from? It looks nontrivial. A more suitable solution could be arrived at by making the circle smaller and sliding it in the direction of the max position until you hit a second circle.
– MNKY
Sep 20 '16 at 21:22
@Vilx- Why are you trying to get the solution to this problem? What is the domain You are bringing it from? It looks nontrivial. A more suitable solution could be arrived at by making the circle smaller and sliding it in the direction of the max position until you hit a second circle.
– MNKY
Sep 20 '16 at 21:22
@Vilx- another possible approximate solution is to find the smallest enclosing rectangle for our circles and use its center as the center of the enclosing circle. It's basic but it's cheap computationally.
– MNKY
Sep 21 '16 at 0:22
@Vilx- another possible approximate solution is to find the smallest enclosing rectangle for our circles and use its center as the center of the enclosing circle. It's basic but it's cheap computationally.
– MNKY
Sep 21 '16 at 0:22
@igael : I was not thinking of rotating rectangles, just axis oriented ones, I edited the sol to explain what I mean.
– MNKY
Sep 21 '16 at 5:27
@igael : I was not thinking of rotating rectangles, just axis oriented ones, I edited the sol to explain what I mean.
– MNKY
Sep 21 '16 at 5:27
I need this for a force-directed graph layout algorithm, and the problem there is pretty much exactly this. I need to group a bunches of nodes (circular) and calculate forces between these groups, taking the size (visual, not count or weight) of the group into account, so that the groups don't overlap.
– Vilx-
Sep 21 '16 at 7:10
I need this for a force-directed graph layout algorithm, and the problem there is pretty much exactly this. I need to group a bunches of nodes (circular) and calculate forces between these groups, taking the size (visual, not count or weight) of the group into account, so that the groups don't overlap.
– Vilx-
Sep 21 '16 at 7:10
 |Â
show 5 more comments
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f1932858%2fhow-to-find-the-smallest-enclosing-circle-over-a-set-of-circles%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Hint: The smallest enclosing circle of a set of points can be found in time O(N Log(N)) using the farthest-point Voronoi diagram. I wouldn't be surprised that this can be generalized to circles of different radii using a weighted Voronoi.
– Yves Daoust
Sep 20 '16 at 7:06
@Vilx- This inf.ethz.ch/personal/emo/DoctThesisFiles/fischer05.pdf is a paper that might help you.
– MNKY
Sep 23 '16 at 13:19
@Vilx- This is a package of an algorithm that solves your problem: people.inf.ethz.ch/gaertner/subdir/software/miniball.html
– MNKY
Sep 23 '16 at 14:29