### Minimal circle

Posted:

**Wed Apr 08, 2009 4:39 pm**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.

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.