From:fc3a501@rzaixsrv1.uni-hamburg.de (Hauke Reddmann)Newsgroups:sci.mathSubject:Re: Of 50 points in the plane, find smallest circle around 45Date:10 Jan 1996 12:55:48 GMTOrganization: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 ICSDate:10 Jan 1996 09:45:55 -0800Newsgroups: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.mathSubject:Re: Of 50 points in the plane, find smallest circle around 45Date:10 Jan 1996 20:03:45 -0500Organization: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 GMTNewsgroups:sci.mathSubject: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: .