|
|
вернуться в форумОбщий форумgiven a set of points
(xi,yi) find a circle with less possible area covering each of these
points
I saw time ago that problem, i thought of the next algorithm:
1. Find the convex hull
2. Get the gravity's center of that convex hull, that will be the
center of the minimal circle
3. from the center to all the points which make the convex hull, find
the largest distance and that will be the radius.
I think that center only will be x = avg(xi), y = avg(yi) since it's
convex polygon. It's not so hard i think :). I only have doubts about
the gravity's center, but is easy to prove that the problem above is
equivalent to:
Given a convex polygon, find the circle with minimal area which
contains it.
Since that convex polygon contains all the points of the set given,
that circle contains all the points. Problem of finding circle with minimal radius, that contains set of
points, can be solved in O(N) Emo Welzl randomized algorithm, and
need not to build convex hull.
Andrey Popyk. > Problem of finding circle with minimal radius, that contains set of
> points, can be solved in O(N) Emo Welzl randomized algorithm, and
> need not to build convex hull.
>
> Andrey Popyk.
> And as I think, centroid doesn't work.
Suppose we have 3 points with coordinates
0 0
0 10
10 0
Real center of our circle is (5.000 ; 5.000)
Center of gravity of Convex Hull this set of points is (3.536 ; 3.536)
Center of gravity of Convex Polygon contains this points is (3.333 ;
3.333)
Center of gravity of this points is (3.333 ; 3.333)
Which center of gravity we must to find if we want to solve mincircle
problem?
Andrey Popyk.
popyk@ief.tup.km.ua > And as I think, centroid doesn't work.
>
> Suppose we have 3 points with coordinates
> 0 0
> 0 10
> 10 0
>
> Real center of our circle is (5.000 ; 5.000)
> Center of gravity of Convex Hull this set of points is (3.536 ;
3.536)
> Center of gravity of Convex Polygon contains this points is
(3.333 ;
> 3.333)
> Center of gravity of this points is (3.333 ; 3.333)
>
> Which center of gravity we must to find if we want to solve
mincircle
> problem?
>
> Andrey Popyk.
> popyk@ief.tup.km.ua
> |
|
|
