Smallest circle covering set of points
in [General Programming]
|
Prev: Heathfield: You're wrong: here's proof: (WAS: Re: Welcome To The Word Wide Mirror Sci.Math)
Next: SETP-10 Call for papers
From: Hans-Bernhard Bröker on 16 Nov 2009 13:14 [F'up2 sorely missing --- fixed] Ray Vickson wrote: > Assuming that checking for points in/out of a circle, computing a new > circle, etc., are considered as "elementary" operations, is the > problem solvable in polynomial time, or would it be NP-hard? It's obviously polynomial (it's O(N^3) even if you to an exhaustive search over all circles defined by three of the given points).
From: Casey Hawthorne on 16 Nov 2009 13:50 Megiddo's Linear-Time Algorithm? -- Regards, Casey
From: Jon Slaughter on 16 Nov 2009 13:55 Andrew Tomazos wrote: > Given a set of points (a1,b1) (a2,b2)..(an,bn) in the plane - what's a > good algorithm for determining the centerpoint and radius of the > smallest circle that will cover all the points? Thanks, Andrew. Note that the circle must contain 2 of the points. It must also contain the longest line segment between any two pairs. The center of the circle must be contained in the convex hull of the points. The diameter of the circle must be larger or equal to the longest line segment. If we assume that any optimal circle must have as points the same points as longest line segment then we have 2 points. This fixes the center of the circle to move along a line that is perpendicular to the line segment between the 2 points and also at it's midpoint. In this case it is very easy to search for the center by subdividing the possible center line and noting that it must fall within the convex hull. My guess is that the center is the midpoint between the intersection of it and the hull. e.g., if it is symmetric then the center is is the midpoint of the largest line segment. I'm not sure if this produces the optimal circle or not and is not unique when there are multiple longest line segments. In terms of convex hulls we are finding the largest line segment contained in it and then finding the midpoint of the line segment perpendicular to the largest line segment that runs through the largest line segment's midpoint.
From: Dann Corbit on 16 Nov 2009 13:55 In article <6bc4f385-4b1d-4c1e-b558- 37479c4dad9f(a)k17g2000yqh.googlegroups.com>, andrew(a)tomazos.com says... > > Given a set of points (a1,b1) (a2,b2)..(an,bn) in the plane - what's a > good algorithm for determining the centerpoint and radius of the > smallest circle that will cover all the points? Thanks, Andrew. Did you read the news:comp.graphics.algorithms FAQ? It's in there.
From: Casey Hawthorne on 16 Nov 2009 14:27
On Mon, 16 Nov 2009 10:55:39 -0800, Dann Corbit <dcorbit(a)connx.com> wrote: >In article <6bc4f385-4b1d-4c1e-b558- >37479c4dad9f(a)k17g2000yqh.googlegroups.com>, andrew(a)tomazos.com says... >> >> Given a set of points (a1,b1) (a2,b2)..(an,bn) in the plane - what's a >> good algorithm for determining the centerpoint and radius of the >> smallest circle that will cover all the points? Thanks, Andrew. > >Did you read the news:comp.graphics.algorithms FAQ? >It's in there. People never seem to read the FAQ's anymore, they just FAQ off! -- Regards, Casey |