3
$\begingroup$

When I was in high school geometry, we had a fun little game on the computer called Green Globs (the website for the software is http://www.greenglobs.net/index.html). A number of targets (globs) are randomly produced, and basically, the point of the game is to enter math equations to destroy targets in the least equations possible; writing an equation that intersects a glob means that it is destroyed. I haven't thought too much about this generalization but I thought it might be fun to examine, and I'm sure some work has been done in some field on a similar type question. The question I would eventually answer is the following :

"Let $R >0$ be a positive real number. Let $n >0$ be an integer. Fix some diameter $d and consider $n$ balls $\{B_i\}_{i=1}^n$ of diameter $d$ placed randomly inside the ball $B(0,R)$ of radius $R$ centered at the origin, such that each ball $B_i$ is contained entirely inside $B(0,R)$. (Intersections of the $B_i$ are acceptable). Fix some number $w$ denoting width.

Given $R,n,d,w$ as above, what is the average number of lines of width $w$ necessary so that at least one line intersects each ball in at least one point?"

Now, I'm sure that in it's full generality as above, the question is quite hard. Perhaps examining specific cases are easier or have already been done. Do you know of any literature on this subject or something similiar?

  • 0
    You don't really need $w$ as an additional parameter. The problem remains the same if you shrink the lines and expand the balls; more precisely, if you consider lines of zero width and balls of diameter $d+w$ in a larger ball of radius $R+w/2$.2012-08-28
  • 0
    @RahulNarain Not exactly true. As an example, if I have have a ball of radius $R$ and I consider a line of width $ w= R$, then only one line will suffice.2012-08-29
  • 0
    By width you mean half-width then?2012-08-29
  • 0
    (Outer radius $R$, inner radius $r = d/2 \ge 0$, line half-width $w = R$) $\mapsto$ (outer radius $2R$, inner radius $r \ge R$, line half-width $0$). Every inner ball contains the center of the outer ball, so one line through the center suffices.2012-08-29
  • 0
    If you have enough, say, horizontal lines to cover the disk, that'll certainly do to intersect all the balls. You can save a little by covering only from $R-d$ down to $-R+d$. This is worst case - you want average case - but if there are enough balls I suspect there's little difference. It may be that there's something in the X-ray tomography literature.2012-08-29
  • 1
    I loved this game in high school! I used to use graphs like $y=\tan(x)$ to get all of the globs in one shot. Sorry, no math content in this comment, just nostalgia.2013-03-18

0 Answers 0