13
$\begingroup$

Intersecting $n$ unit-radius cylinders, each with axis through the origin, produces a shape circumscribed about a unit-radius sphere:

   Cyl12

My question is:

For each $n$, which arrangement of cylinders minimizes the Pompeiu–Hausdorff distance to the sphere?

This Hausdorff distance is the smallest $r$ such that each set is contained within an $r$-neighborhood of the other. For the above $2$-cylinder example, I believe the Hausdorff distance is $\sqrt{2}-1$.

For $n=3$, there are two natural candidates: orthogonal cylinder axes, and axes in a plane at $60^\circ$:

Cyl123Cyl145

I calculate the Hausdorff distances to the sphere to be $\sqrt{\frac{3}{2}}-1$ and $\frac{2}{\sqrt{3}}-1$ respectively, approximately $0.22$ and $0.15$. If I'm not miscalculating, it is a bit of a surprise that the second arrangement is closer to the sphere.

$\endgroup$
2
  • 1
    $\begingroup$ This paper answers a closely related but different question (different as far as I can see): Jang, Z., Polyanskii, A. Proof of László Fejes Tóth’s zone conjecture. Geom. Funct. Anal. 27, 1367–1377 (2017). DOI. $\endgroup$ Sep 22 at 12:11
  • 1
    $\begingroup$ How about simply minimizing the volume? This is somewhat reminiscent of the problem mentioned here in the “PS” of finding the least possible volume cut by $n$ planes all tangent to the unit sphere, but even this (seemingly simpler?) problem does not seem to have a known answer. $\endgroup$
    – Gro-Tsen
    Sep 26 at 15:53

3 Answers 3

4
$\begingroup$

According to RavenclawPrefect's answer, we need to choose the unit vectors $a_1,a_2,\dots,a_n$ so as to minimize the maximal value of $$ f(v)=\min\langle v,a_i\rangle, $$ over $v\in S^2$. If $\cos \alpha$ is the answer to this optimizational problem, then the sets $$ Z_i=\{v\in S^2\colon \langle v,a_i\rangle\leq\cos\alpha\} $$ cover the sphere.

The set $Z_i$ is a zone on the sphere: a `strip' of angular width $2\alpha$. Here I use the terminology from this nice paper by Jiang and Polyanskii.

In that paper, the authors show that, if $n$ zones cover the sphere, then the sum of their widths is at least $\pi$, thus establishing Fejes Toth's conjecture. Thus, if the (equal) zones corresponding to $a_1,\dots,a_n$ cover the sphere, their widths should be at least $\pi/n$. So, for any tuple $(a_1,a_2,\dots,a_n)$ there is a vector whose angle with each of them is at most $\pi/2-\pi/(2n)$.

This shows that the $n$ cylinders rotated by equal angles aroung the same axis indeed provide an optimal arrangement.

$\endgroup$
1
  • $\begingroup$ Nice! So in some sense my question ended up to be a relatively minor variation on Fejes Tóth's zone conjecture. $\endgroup$ Sep 26 at 21:11
7
$\begingroup$

Not a proof, but some thoughts on how to get empirical data for this problem and evidence for the optimal configuration:

Suppose we have a matrix $C$ whose rows are the unit vectors pointing in the directions of our cylinders. Then computing the Hausdorff distance amounts to finding, among unit vectors $v$ in space, the one which maximizes

$$\min_{c_i\in C}\frac{1}{\sqrt{1-||v\cdot c_i||^2}}$$

If we want to approximate this with a collection of random unit vectors given by rows in a matrix $V$, then this amounts to performing some simple element-wise arithmetic on the matrix $CV^T$, which means that it's quite fast to throw into any framework for doing matrix multiplications efficiently.

I initialized $1000$ random cylinder positions (forcing WLOG the first cylinder to point along $[1,0,0]$ and the second to be in the $xy$-plane), evaluating their score by taking the maximum radius along any of $100,000$ random vectors.

I then took the best of these initial candidates, made random small adjustments to some of the coordinates, and kept the change if it improved the score. (As the changes got smaller, I started re-scoring any candidates that looked like they were the best yet, since you're also putting a lot of selection on "drawing a lucky set of random vectors" and can get unrealistically good scores.)

The winner had cylinders pointed along the following vectors:

[ 1.          0.          0.        ]
[ 0.49990595 -0.8660797   0.        ]
[ 0.50013575  0.86594231 -0.00285279]

This seems like pretty strong evidence that the proposal in the original post is optimal.

With four cylinders, the winning candidate looked like:

[ 1.          0.          0.        ]
[ 0.00114353  0.99999935  0.        ]
[-0.7066738   0.70753928 -0.00054313]
[ 0.70754814  0.70600075  0.03063601]

This is very close to arranging the cylinders in a regular octagon in the $xy$-plane (and doesn't score better than doing so exactly).

With five cylinders:

[ 1.          0.          0.        ]
[-0.80883904 -0.58803011  0.        ]
[ 0.30972531 -0.9506074  -0.0203915 ]
[-0.80888608  0.58783778 -0.01224957]
[-0.30840091 -0.95123839 -0.00586572]

In general with $k$ cylinders, placing them at equally spaced intervals in a plane will acheive a Hausdorff distance of $\sec\left(\frac{\pi}{2k}\right)-1$, while placing $k-1$ of them equally spaced in the $xy$-plane and one of them vertically will acheive a distance of $\sqrt{1+\sin^2(\frac{\pi}{2(k-1)})}-1$, which is strictly worse for $k\ge 3$.

$\endgroup$
1
  • $\begingroup$ Very nice analysis! And $\sec\left(\frac{\pi}{2k}\right)-1$ is $\frac{2}{\sqrt{3}}-1$ when $k=3$, in agreement with my calculation. $\endgroup$ Sep 16 at 19:15
0
$\begingroup$

Place a pin through a cylindrical straw, passing through the axis and perpendicular thereto. When you revolve the straw around the pin, you trace a sphere with the straw contained entirely outside.

Distributing $n$ cylinders at equal angles around such an axis will give a good approximation to this spherical envelope.

$\endgroup$
2
  • $\begingroup$ Looks like not everyone can place a pin in a straw ... . $\endgroup$ Sep 21 at 14:22
  • 3
    $\begingroup$ I like the construction, but of course it doesn't answer whether it achieves the optimal Hausdorff distance. $\endgroup$ Sep 22 at 13:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.