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