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
Part of
Geometry in Action,
a collection of applications of computational geometry.
David Eppstein,
Theory Group,
ICS,
UC Irvine.
Last update: .