6
$\begingroup$

Imagine a number of chords of a sphere $S$ which nearly, but not quite, pass through the center of $S$, in such a way that no pair of chords intersect:
      50 chords
I would like to connect pairs of chord endpoints by noncrossing paths on the surface of $S$ so that the paths + the chords form a cycle. I can prove (for example, by induction) that this is always possible if I am permitted to use arbitrary paths on the surface. But what I would really like to achieve is connecting the chord endpoints by noncrossing arcs of great circles.

Henceforth consider the chords to pass exactly through the center of $S$, but pretend they do not intersect there. An example is shown left below, where three axes-chords are connected into a cycle. The example right below of coplanar chords shows that what I want to achieve is not always possible.
    ChordCycles

Q. Under what conditions can a set of chords through the center of $S$ be connected into a single cycle by noncrossing arcs of great circles? In particular, can this be achieved if no three chord endpoints lie on a great circle, i.e., are in general position in this sense?

There is a considerable literature on noncrossing geometric matchings in the plane, but I don't see that it applies to my question. Any pointers, ideas, or counterexamples welcomed!

(This arose in an investigation related (nonobviously) to an earlier question, "Untangling entwined rigid chains in 3-space".)

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ Is it relevant/necessary that the points are on a sphere and chords are connecting nearly antipodal points? What if there are $2n$ points in "general position" in the plane and they are colored by $n$ colors, 2 points of each color. Can we always find a perfect matching of non-crossing line segments such that a walk that alternates between following a line segment and jumping to the other point of the same color will connect the points to a single cycle? $\endgroup$
    – Johan Wästlund
    Commented Jun 28, 2013 at 14:04
  • $\begingroup$ That's a wonderfully clarifying reformulation of the essence of the discrete geometry question at the heart of this! $\endgroup$
    – Joseph O'Rourke
    Commented Jun 28, 2013 at 14:41
  • 1
    $\begingroup$ Answering my own question: When $n\geq 2$, the convex hull is spanned by at least 3 points, so we can find two of them that are adjacent and of different color, say red and green. After pairing them up, we solve the subproblem of the remaining $2n-2$ points under red-green color blindness (treating the other red and green points as having the same color). $\endgroup$
    – Johan Wästlund
    Commented Jun 28, 2013 at 18:03
  • 1
    $\begingroup$ One may pose a related question about a finite subset of the projective plane and the arcs of the straight lines--there are just simple points, no notion of any antipodal points. The questions are essentially different but at least they are similar, and the projective version has simpler formulation I'd think (a single projective point is something of a substitute, not exactly, of an antipodal pair). $\endgroup$
    – Włodzimierz Holsztyński
    Commented Jun 29, 2013 at 3:37

1 Answer 1

Reset to default
4
$\begingroup$

Among the perfect matchings (with great-circle arcs) that give a single cycle when combined with the chords, consider the one that has minimum total length. Suppose that two of the arcs are crossing, say AB and CD cross at the point X. Then consider replacing these two arcs either by AC+BD or by AD+BC. One of these possibilities (say AC+BD) must again give a single cycle when combined with the chords. And except in "degenerate" cases, the total length of AC+BD will be smaller than that of (AX+XC)+(BX+XD) = (AX+XB)+(CX+XD). The contradiction shows that if the points are in "general position", the desired non-crossing matching with arcs of great circles is possible.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Johan, it's very nice (I even upvoted your answer). But if a cycle is understood as a connected cycle then the question is still open. $\endgroup$
    – Włodzimierz Holsztyński
    Commented Jun 29, 2013 at 3:30
  • $\begingroup$ Wlodzimierz, I don't understand, what is the difference between cycle and connected cycle? I'm looking at pairings of the points using (possibly crossing) great circle arcs, under the condition that together with the chords they connect the points into a single cycle (rather than several cycles). I'm arguing that among those pairings, the one that minimizes the total length of the arcs is non-crossing (except in the degenerate case illustrated in the OP). $\endgroup$
    – Johan Wästlund
    Commented Jun 29, 2013 at 7:12
  • $\begingroup$ Brilliant, Johan! This is essentially the proof that the TSP is noncrossing. You are assuming there exists at least one possibly crossing cycle to get your proof off the ground, but in fact I can modify the argument for arbitrary paths to achieve that. $\endgroup$
    – Joseph O'Rourke
    Commented Jun 29, 2013 at 13:21

You must log in to answer this question.

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