What is the meaning of "from distinct vertex chains" in this nearest neighbor algorithm?

Question

The following pseudo-code is from the first chapter of an online preview version of The Algorithm Design Manual (page 7 from this PDF).

The example is of a flawed algorithm, but I still really want to understand it:

[...] A different idea might be to repeatedly connect the closest pair of endpoints whose connection will not create a problem, such as premature termination of the cycle. Each vertex begins as its own single vertex chain. After merging everything together, we will end up with a single chain containing all the points in it. Connecting the final two endpoints gives us a cycle. At any step during the execution of this closest-pair heuristic, we will have a set of single vertices and vertex-disjoint chains available to merge. In pseudocode:

ClosestPair(P)     Let n be the number of points in set P.     For i = 1  to n − 1 do         d = ∞         For each pair of endpoints (s, t) from distinct vertex chains             if dist(s, t) ≤ d then sm = s, tm = t, and d = dist(s, t)         Connect (sm, tm) by an edge     Connect the two endpoints by an edge 

Please note that sm and tm should be sm and tm.

First of all, I don't understand what "from distinct vertex chains" would mean. Second, i is used as a counter in the outer loop, but i itself is never actually used anywhere! Could someone smarter than me please explain what's really going on here?

Answer 1

This is how I see it, after explanation of Ernest Friedman-Hill (accepted answer):

So the example from the same book (Figure 1.4). I've added names to the vertices to make it clear

So at first step all the vertices are single vertex chains, so we connect A-D, B-E and C-F pairs, b/c distance between them is the smallest.

At the second step we have 3 chains and distance between A-D and B-E is the same as between B-E and C-F, so we connect let's say A-D with B-E and we left with two chains - A-D-E-B and C-F

At the third step there is the only way to connect them is through B and C, b/c B-C is shorter then B-F, A-F and A-C (remember we consider only endpoints of chains). So we have one chain now A-D-E-B-C-F.

At the last step we connect two endpoints (A and F) to get a cycle.

Answer 2

1) The description states that every vertex always belongs either to a "single-vertex chain" (i.e., it's alone) or it belongs to one other chain; a vertex can only belong to one chain. The algorithm says at each step you select every possible pair of two vertices which are each an endpoint of the respective chain they belong to, and don't already belong to the same chain. Sometimes they'll be singletons; sometimes one or both will already belong to a non-trivial chain, so you'll join two chains.

2) You repeat the loop n times, so that you eventually select every vertex; but yes, the actual iteration count isn't used for anything. All that matters is that you run the loop enough times.