Minimal circle

Let's talk about algorithms!

Moderator: Board moderators

Post Reply
slxst
New poster
Posts: 23
Joined: Mon Oct 16, 2006 2:18 am

Minimal circle

Post by slxst » 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.

fingon
New poster
Posts: 2
Joined: Wed Jun 17, 2009 7:39 pm

Re: Minimal circle

Post by fingon » Wed Jun 17, 2009 8:41 pm

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.

dynamical
New poster
Posts: 1
Joined: Sun Jul 19, 2009 7:15 pm

Re: Minimal circle

Post by dynamical » Sun Jul 19, 2009 7:20 pm

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.)

Post Reply

Return to “Algorithms”