5
$\begingroup$

Let $S$ be a unit-radius sphere in $\mathbb{R}^3$.

Q0. Where should one place $3$ disjoint lines intersecting $S$ to minimize the maximum distance between any two points in $S$, where distance is measured as follows. Distance off the lines is Euclidean distance, but the distance between any two points on one line is zero.

The lines are like very fast transportation tubes. (I have in mind Star Wars' Coruscant.)

With no tubes, the maximum distance is $2$, realized by any antipodal pair. One tube, or two tubes, do not help reduce the maximum, but three tubes seem to help. In particular, I believe if one selects the three tubes to be the $x,y,z$ axes, slightly displaced to satisfy disjointness, then the maximum distance is $2 \sqrt{\frac{2}{3}} + \epsilon \approx 1.63$, illustrated below.

Q1. Is there a better arrangement of the three tubes?


          Tubes
          The red point is the origin/center of the sphere. The point $(1,1,1)/\sqrt{3}$ is $\sqrt{\frac{2}{3}}$ (green) from each axis.
The natural generalization is: $d$ tubes intersecting a unit-radius sphere in $\mathbb{R}^d$.

$\endgroup$
7
  • $\begingroup$ (I posed a variant of this question at the 2017 Canadian Conference on Computational Geometry.) $\endgroup$ Jul 31, 2017 at 20:23
  • $\begingroup$ I recommend an alternate formulation to clarify (or contrast): take a space geodesic path (so perpendiculars off a tube to a point on the surface or on another tube) and distance will be the min of the sum of the perpendiculars. Your mention of sphere makes me think of walking on the surface to a tube entrance, not burrowing down to the tube. Gerhard "Is Exhausted By Public Transportation" Paseman, 2017.07.31. $\endgroup$ Jul 31, 2017 at 20:39
  • $\begingroup$ @GerhardPaseman: Yes, precisely a space geodesic path: nice formulation! $\endgroup$ Jul 31, 2017 at 20:42
  • $\begingroup$ I like this formulation even better; I recommend that you include it in your post. Given d, How small a radius r is needed to cover a unit d-ball with d cylinders of radius r and height 2 ? If this question is not equivalent to yours, it should provide a method for a nice upper bound. Gerhard "Finds Covering Problems More Intuitive" Paseman, 2017.07.31. $\endgroup$ Aug 1, 2017 at 2:37
  • $\begingroup$ @Gerhard: I do not think the last reformulation is the same, since you can switch from one tube to another one (can you?)... $\endgroup$ Sep 21, 2017 at 16:11

1 Answer 1

1
$\begingroup$

Thanks to Ilya Bogdanov, I have faced this problem more squarely. He (gender presumption) had me convinced that my cylinder reformulation was not equivalent. It may not be, but I think it helps solve the posted problem.

Note that the metric stated in the problem always involves the distance from a point on the sphere to a tube. Two points which normally might be close on the sphere will be about distance 2R apart, where R approximates the distance from either point to the nearest tube.

An earlier non-visible attempt at this analysis considered the distances between tubes, and attempted to account for the differences. However, for most configurations of tubes, we can dispense with these transfer point distances by observing that there are 2^d many points on the d sphere that are equidistant from all (also assuming a sufficiently small tube radius) tubes. (One can find tube configurations where this is not true, however I conjecture that none of these provide an optimal arrangement.) Then there is a pair of points which is at least (and in fact exactly) R+S apart, where I pick R and S as the two largest of these 2^d equidistances.

I now conjecture that for any configuration that has these distances, an optimal configuration has R=S. We now have moved into covering the sphere by cylinders of constant radius. At this writing, I leave the numerics to others, as well as resolving the conjectures.

Gerhard "Has No Computer Geometry System" Paseman, 2017.09.21.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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