3
$\begingroup$

Imagine I take a sheet of paper and use a pin to generate an $N$x$M$ rectangular array of small holes. I then fold the sheet to form a cylinder of radius $r_c$ and height $h_c$, where there are $N$ pinholes around its circumference and $M$ pinholes from the top of the cylinder to the bottom. No edge-effects from the folding process are discernible.

Now, say I pick a coordinate, $C$, in the three-dimensional space inside the cylinder. $C$ is some distance from the bottom of the cylinder, $A$, and some distance from the central-axis of the cylinder, $B$. I then proceed to shine a laser, or thread a very thin string between two pinholes, $(p_1, p_2)$, such that the beam or the string is as close as possible to $C$. Here, the laser or the string can be treated as a one-dimensional chord in the interior of the cylinder.

How do I choose $(p_1, p_2)$ to generate a line containing a coordinate $C*$ as close as possible to my chosen coordinate $C$? In general, how well can I do as a function of the density of the pinhole array and the position of the coordinate in terms of $A$ and $B$? Pressing my luck, in terms of minimizing the (straight-line) difference between $C$ and $C^*$, are there better geometries for the pinholes than a rectangular array?

Update: First of all, thanks to Joseph O'Rourke for the awesome graphic! Secondly, I would be very interested in an analysis of worst-case delta with excluded regions, say, at the top and bottom of the cylinder (as Gerhard Paseman suggested).

Update 2: Joseph O'Rourke states a two-dimensional variant of this problem in Part 2 (P2) of his question "Chord arrangement that avoids confining small or large disks", (Chord arrangement that avoids confining small or large disks).

Improve this question
$\endgroup$
5
  • $\begingroup$ Since Joseph O'Rourke was kind enough to provide one picture of your problem, you might ask him for five more: one where the array is based on diamonds instead of a rectangular grid, one using a hexagonal array, and then copies of each of these with the lines given a thickness of delta/4, where delta is the largest distance between any point inside the cylinder and its nearest line. Hopefully he can compute delta for some reasonable spacing of the N vertical points in the three configurations. Gerhard "Ask Me About System Design" Paseman, 2011.10.01 $\endgroup$
    – Gerhard Paseman
    Commented Oct 2, 2011 at 4:51
  • 1
    $\begingroup$ Seems unlikely to have a closed-form solution. Even the 2-dimensional projection (find a diagonal of a regular $N$-gon nearest to a given interior point) leads to an exotic Diophantine problem (more-or-less finding the point $(x/N,y/N)$ nearest to a given transcendental curve). Where does this question arise, and what are typical sizes of $M$ and $N$?$$ $$A lower bound, and possibly a reasonable approximation, for the typical minimal distance is the radius of cylinders about each string the sum of whose volumes is within a constant factor of the volume of the cylinder. $\endgroup$
    – Noam D. Elkies
    Commented Oct 2, 2011 at 4:59
  • $\begingroup$ Thinking some more, it seems to me that the largest distance needed will be at the top or at the bottom of the cylinder: I see this by looking at the graph on 2n vertices mentioned in another comment. If the original poster is willing to exclude such regions, he or she may find delta quite small even for small values of n. Gerhard "Ask Me About System Design" Paseman, 2011.10.01 $\endgroup$
    – Gerhard Paseman
    Commented Oct 2, 2011 at 5:12
  • $\begingroup$ I wonder if this problem is motivated by radiation therapy? $\endgroup$
    – Joseph O'Rourke
    Commented Oct 2, 2011 at 13:11
  • $\begingroup$ As Noam suggests, this question seems interesting already in 2D. I've taken the liberty of posing a version (actually, two versions) separately. $\endgroup$
    – Joseph O'Rourke
    Commented Oct 2, 2011 at 15:05

2 Answers 2

Reset to default
3
$\begingroup$

This adds nothing to your interesting question, but I couldn't resist illustrating the network of lines ($n=8$, $m=4$):
          Cylinder

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Actually it brings to mind a work of Poonen et al on the number and arrangement of diagonals of regular n-gons. I do not recall the exact reference, but something about there being at most 6 concurrent diagonals comes to mind, excepting the center. It might say how many interior regions and may give other clues to an answer. Perhaps someone else will provide the reference and more detail. Gerhard "Ask Me About System Design" Paseman , 2011.10.01 $\endgroup$
    – Gerhard Paseman
    Commented Oct 2, 2011 at 4:32
  • $\begingroup$ Also, one can devise a coordinate system and break the problem into vertical (2n complete bipartite plus regular grid graph) and horizontal (m complete regular polygonal graph). components. Although I had the idea before, your picture nicely suggests such a break down of the problem. Gerhard "Likes To See Pretty Pictures" Paseman, 2011.10.01 $\endgroup$
    – Gerhard Paseman
    Commented Oct 2, 2011 at 4:39
2
$\begingroup$

I shall outline an approach to answering some forms of this question, and leave verification and actual computations to others who are more energetic than I feel at present.

The original presentation of points arranged in an n by m rectangular grid makes for a particularly pleasing analysis of the quantity delta, which I define as the maximum over all points p inside the cylinder of d(p) which is the minimum over all lines between two points in the pinhole grid of the distance between p and such a line. Namely, when you project the point and configuration on the horizontal plane to get a point q in or near a regular n-gon, and choose the three or more nearest n-gon diagonals to the projected point, compute d_i which is q's distance for each of these, and then use these choices to look at the projection of p onto each of the vertical planes containing these lines to determine some distances d_j among the grid graphs with their diagonals. delta can then be figured or at least approximated using d_i and d_j, likely delta^2 = minimum of d_i^2 + d_j^2 over an appropriate set of choices for i and j. I expect the d_is for large n to be O(n^(-3/2)) times the radius of the cylinder and the d_js to be at most O(1/m) times the minimum of height and length of the smallest rectangle in the largest of the grid graph projections used, unless one is looking at the top or bottom region, in which case replace 1/m by 1.

For some of the alternate geometries I suggested in a comment, one does not get as nice a decomposition, but they contain one or more copies of the originally suggested geometry, so one can get a rough value of delta using a sub configuration of pinholes, and then refine that estimate by using more pinholes as needed. An O(nm) way of doing that is by picking a pinhole, computing the interesting intersection of the line containing the interior point and the pinhole with the cylinder, and then finding the k closest pinholes to that intersection; doubtless there are refinements to this approach that will allow a speedier estimation of delta.

In fact, this approach (peeking through each pinhole at the point p) suggests that maximal delta will be near the center of the cylinder and will still be a value something like 1/4 the minimum of the height and width of the bounding rectangle (the four pinholes one sees as being "nearest" to the image of the chosen point). The nice thing about this approach is that it can be used on arbitrary pinhole arrangements, and choosing a random selection of pinholes from which to view will often get a quick and good upper bound on d(p) for a given point p.

Gerhard "Ask Me About Pinhole Peeking" Paseman, 2011.10.02

Improve this answer
$\endgroup$
2
  • $\begingroup$ @Gerhard Paseman, do you think the case of peeping through holes between two equivalent planar parallel sheets (held some fixed distance apart) would be more tractable? $\endgroup$
    – UltraBlue06
    Commented Oct 3, 2011 at 6:15
  • $\begingroup$ In computing delta? I suspect not. However, the geometry may indicate some other interesting pattern of lacunae. You might try a few small examples. Alternatively, if you can provide more motivation, I may have an idea that addresses the motivation. Gerhard "Ask Me About System Design" Paseman, 2011.10.03 $\endgroup$
    – Gerhard Paseman
    Commented Oct 3, 2011 at 7:17

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .