Geometry in Action


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