Page 1 of 1

Minimal circle

Posted: Wed Apr 08, 2009 4:39 pm
by slxst
Minimal Circle

http://acm.zju.edu.cn/onlinejudge/showP ... mCode=1450

What I was thinking is:

for n <= 3 points I used the obvious formulas. For n > 3:

First to use the Akl Touissant heuristic to calculate Convex Hull (look for the 4 extreme points and remove any interior points to that quadrilateral)
Then brute force every trio of points to know if the circle that they define is in fact the circle with minmal area.

In all places it is said that the Heuristic takes O(n) time but how do I do it!

Is there a better approach?

Thanks.

Re: Minimal circle

Posted: Wed Jun 17, 2009 8:41 pm
by fingon
The minimum circle has that property that it goes through 3 different points, it's easy to proof that some circle isn't optimal if it goes through one or two points, you can shrink it until it goes through 3 points.
There is exactly one circle going through 3 different points. It's possible to find circle going through 3 points when points are given, you got to solve 3 equations.
Here goes O(n^3) algorithm.
Compute convex hull, for every 3 points on hull, find circle and compute it's area.


Forgive me my language skills.

Re: Minimal circle

Posted: Sun Jul 19, 2009 7:20 pm
by dynamical
There is a similar problem in CEOI 2006. (ANTENNA)
The solution is using binary search and sweeping, which gives the time complexity O(N^2 log N * log T).
(T is the maximum possible radius to cover all the points.)