I have this problem where I have random points on a 2-D plane and i have to find the circle which is closest to all the Points. I have brute force solution of it which goes like this : ↵
1) Select two sets of two points.↵
2) Calculate the perpendicular bisector for each pair.↵
3) Determine the intersection point of these two perpendicular bisectors (one from each set).↵
4) Verify if the intersection point serves as the center of a circle where the minimum and maximum distances from all points to this center correspond to the points chosen in step 1).↵
5) If the condition in step 4) holds true, then the intersection point becomes the center of the circle closest to the points, with its radius calculated as half the difference between the maximum and minimum distances plus the minimum distance."↵
↵
The overall worst case time complexity comes out to be `O(n^5)`. I have found a way to reduce the average case time complexity by utilizing the fact that the outer most 2 point out of the final 4 point that we get will always lie on the Convex hull but the worst case time complexity still remains the same.↵
↵
Here is the ↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
double finn, radd ;↵
pair<double,double> ff,ans;↵
finn = INT_MAX;↵
p1={0,0};↵
p2={0,0};↵
p3={0,0};↵
p4={0,0};↵
for(i=0;i<v.size();i++)↵
{↵
for(j=0;j<v.size();j++)↵
{↵
for(k=0;k<v.size();k++)↵
{↵
for(l=0;l<v.size();l++)↵
{↵
if(v[i]!=v[j] && v[k] != v[l] && v[i] != v[k] && v[i] != v[l] && v[j] != v[k] && v[j] != v[l])↵
{↵
m1 = (v[j].F - v[i].F)/(v[i].S - v[j].S); ↵
m2 = (v[l].F - v[k].F)/(v[k].S - v[l].S); ↵
x1net = (v[i].F + v[j].F)/2;↵
x2net = (v[k].F + v[l].F)/2;↵
y1net = (v[i].S + v[j].S)/2;↵
y2net = (v[k].S + v[l].S)/2;↵
xfinal = ((y2net - y1net) + (m1*x1net - m2*x2net))/(m1 - m2);↵
yfinal = m1*xfinal - m1*x1net + y1net;↵
ff = mp(xfinal,yfinal);↵
↵
mx=0;↵
mxx=INT_MAX;↵
for(m=0;m<v.size();m++)↵
{↵
ndist = dist(ff,v[m]);↵
if(ndist>mx)↵
mx= ndist;↵
if(ndist<mxx)↵
mxx=ndist;↵
↵
↵
↵
}↵
mxxx = mx - (mx + mxx)/2;↵
// cout<<ff.F<<" "<<ff.S<<" RAD: "<<mxxx<<x;↵
if(mxxx < finn)↵
{finn=mxxx;↵
ans=ff;↵
radd = (mx + mxx)/2;↵
p1=v[i];↵
p2=v[j];↵
p3=v[k];↵
p4=v[l];↵
↵
// cout<<ans.F<<" "<<ans.S<<x;↵
↵
↵
↵
}↵
↵
}↵
else↵
continue;↵
↵
}↵
}↵
}↵
}↵
cout<<"Minimum distance from each point : ";↵
cout<<finn<<xx;↵
cout<<"Radius : "<<radd<<" centre : ("<<ans.F<<" , "<<ans.S<<")"<<xx;↵
~~~~~↵
↵
↵
</spoiler>↵
↵
A sample image where i have random point and with the minimum distance circle. ↵
↵
↵
↵
Is there any way that i can reduce the time complexity?
1) Select two sets of two points.↵
2) Calculate the perpendicular bisector for each pair.↵
3) Determine the intersection point of these two perpendicular bisectors (one from each set).↵
4) Verify if the intersection point serves as the center of a circle where the minimum and maximum distances from all points to this center correspond to the points chosen in step 1).↵
5) If the condition in step 4) holds true, then the intersection point becomes the center of the circle closest to the points, with its radius calculated as half the difference between the maximum and minimum distances plus the minimum distance."↵
↵
The overall worst case time complexity comes out to be `O(n^5)`. I have found a way to reduce the average case time complexity by utilizing the fact that the outer most 2 point out of the final 4 point that we get will always lie on the Convex hull but the worst case time complexity still remains the same.↵
↵
Here is the ↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
double finn, radd ;↵
pair<double,double> ff,ans;↵
finn = INT_MAX;↵
p1={0,0};↵
p2={0,0};↵
p3={0,0};↵
p4={0,0};↵
for(i=0;i<v.size();i++)↵
{↵
for(j=0;j<v.size();j++)↵
{↵
for(k=0;k<v.size();k++)↵
{↵
for(l=0;l<v.size();l++)↵
{↵
if(v[i]!=v[j] && v[k] != v[l] && v[i] != v[k] && v[i] != v[l] && v[j] != v[k] && v[j] != v[l])↵
{↵
m1 = (v[j].F - v[i].F)/(v[i].S - v[j].S); ↵
m2 = (v[l].F - v[k].F)/(v[k].S - v[l].S); ↵
x1net = (v[i].F + v[j].F)/2;↵
x2net = (v[k].F + v[l].F)/2;↵
y1net = (v[i].S + v[j].S)/2;↵
y2net = (v[k].S + v[l].S)/2;↵
xfinal = ((y2net - y1net) + (m1*x1net - m2*x2net))/(m1 - m2);↵
yfinal = m1*xfinal - m1*x1net + y1net;↵
ff = mp(xfinal,yfinal);↵
↵
mx=0;↵
mxx=INT_MAX;↵
for(m=0;m<v.size();m++)↵
{↵
ndist = dist(ff,v[m]);↵
if(ndist>mx)↵
mx= ndist;↵
if(ndist<mxx)↵
mxx=ndist;↵
↵
↵
↵
}↵
mxxx = mx - (mx + mxx)/2;↵
// cout<<ff.F<<" "<<ff.S<<" RAD: "<<mxxx<<x;↵
if(mxxx < finn)↵
{finn=mxxx;↵
ans=ff;↵
radd = (mx + mxx)/2;↵
p1=v[i];↵
p2=v[j];↵
p3=v[k];↵
p4=v[l];↵
↵
// cout<<ans.F<<" "<<ans.S<<x;↵
↵
↵
↵
}↵
↵
}↵
else↵
continue;↵
↵
}↵
}↵
}↵
}↵
cout<<"Minimum distance from each point : ";↵
cout<<finn<<xx;↵
cout<<"Radius : "<<radd<<" centre : ("<<ans.F<<" , "<<ans.S<<")"<<xx;↵
~~~~~↵
↵
↵
</spoiler>↵
↵
A sample image where i have random point and with the minimum distance circle. ↵
↵
↵
↵
Is there any way that i can reduce the time complexity?
