Smallest circle around most points
From: fc3a501@rzaixsrv1.uni-hamburg.de (Hauke Reddmann)
Newsgroups: sci.math
Subject: Re: Of 50 points in the plane, find smallest circle around 45
Date: 10 Jan 1996 12:55:48 GMT
Organization: University of Hamburg -- Germany
FolsomMan (folsomman@aol.com) wrote:
: I got this problem from the gatling gun business. They fire 1 second
: bursts (about 50 rounds in the first second, 70 per thereafter) at an
: electronic target that records the point at which each round pierces the
: target plane. The specification required that a certain percentage had to
: fall within a certain size circle. The computer folks tried and failed
: (and so did I) to find any method short of brute force or the human
: eyeball (the standard method) to find the smallest circle enclosing 90
: percent of the impact points. Can you?
I suggest:
1. Define a cartesian coordinate system.
2. Get the coordinates of the points.
3. Compute the mean: x=sum(x_i)/n,y=...
4. Compute the distances from (x,y) and call them r_i.
5. Compute the mean of r_i.
6. Compute the variance of r_i. Call it s.
7. Now draw a circle around x,y with radius s.
It contains about 2/3 of the r_i values.
Radius 2s cointains about 90%,etc. Adjust the factor
before s to get experimentally about 90% of the points.
Happy fragging!
--
Hauke Reddmann fc3a501@math.uni-hamburg.de
<:-EX8
From: eppstein@ics.uci.edu (David Eppstein)
Organization: UC Irvine Department of ICS
Date: 10 Jan 1996 09:45:55 -0800
Newsgroups: sci.math
FolsomMan (folsomman@aol.com) wrote:
: I got this problem from the gatling gun business. They fire 1 second
: bursts (about 50 rounds in the first second, 70 per thereafter) at an
: electronic target that records the point at which each round pierces the
: target plane. The specification required that a certain percentage had to
: fall within a certain size circle. The computer folks tried and failed
: (and so did I) to find any method short of brute force or the human
: eyeball (the standard method) to find the smallest circle enclosing 90
: percent of the impact points. Can you?
Look up
"On geometric optimization with few violated constraints",
Jirka Matou\v{s}ek,
10th ACM Symp. Computational Geometry, 1994, pp. 312-321, and
Discrete & Computational Geometry, vol. 14, 1995, pp. 365-84.
--
David Eppstein UC Irvine Dept. of Information & Computer Science
eppstein@ics.uci.edu http://www.ics.uci.edu/~eppstein/
From: folsomman@aol.com (FolsomMan)
Newsgroups: sci.math
Subject: Re: Of 50 points in the plane, find smallest circle around 45
Date: 10 Jan 1996 20:03:45 -0500
Organization: America Online, Inc. (1-800-827-6364)
An additional point comes to mind as a result of a reply I got by E-mail.
The target was evaluated for two parameters: the shift and the dispersion.
Shift is measured from a laser boresight point and dispersion is *not*
measured from the boresight point, but rather from the center of the
smallest circle enclosing the 45 points.
From: flpalmer@ripco.com (Frank Palmer)
Date: Sat, 13 Jan 1996 07:25:15 GMT
Newsgroups: sci.math
Subject: Re: Of 50 points in the p
In article: <4d0d0k$9pe@rzsun02.rrz.uni-hamburg.de>
fc3a501@rzaixsrv1.uni-hamburg.de (Hauke Reddmann) Writes:
Fc> FolsomMan (folsomman@aol.com) wrote:
Fc> : I got this problem from the gatling gun business. They fire 1
Fc> second : bursts (about 50 rounds in the first second, 70 per
Fc> thereafter) at an : electronic target that records the point at which
Fc> each round pierces the : target plane. The specification required that
Fc> a certain percentage had to : fall within a certain size circle. The
Fc> computer folks tried and failed : (and so did I) to find any method
Fc> short of brute force or the human : eyeball (the standard method) to
Fc> find the smallest circle enclosing 90 : percent of the impact points.
Fc> Can you?
Fc> I suggest:
Fc> 1. Define a cartesian coordinate system.
Fc> 2. Get the coordinates of the points.
Fc> 3. Compute the mean: x=sum(x_i)/n,y=...
Fc> 4. Compute the distances from (x,y) and call them r_i.
Fc> 5. Compute the mean of r_i.
Fc> 6. Compute the variance of r_i. Call it s.
Fc> 7. Now draw a circle around x,y with radius s.
Fc> It contains about 2/3 of the r_i values.
Fc> Radius 2s cointains about 90%,etc. Adjust the factor
Fc> before s to get experimentally about 90% of the points.
Nice, assuming something like normal distribution.
The problem is that the center of the smallest circle is
not necessarily the mean.
I wonder whether the criterion is most effectively met
by the posted question. If they want some % within a
certain-sized circle, then only THAT sized circle must be
considered. Fix that radius as R.
Calculate the mean, are enough holes within the circle of
radius R about that point.
YES => done.
NO => what is nearest hole? Does moving the circle to
cover that increase the number within circle?
etc. etc.
___ Blue Wave/QWK v2.12
--
Frank Palmer
flpalmer@ripco.com
