nearest-neighbor algorithm efficiency I'm starting to read Steven Skiena's Algorithm Design Manual, and one of the examples discusses the nearest-neighbor solution to planing a route that visits each in a set of points and ends up back where it started.
The algorithm starts at some point, travels to the nearest neighboring point, then continues, traveling at each step to the nearest unvisited point, and finally returns to the initial point.
It's not the optimal solution (far from it), but the book mentions that 

... it looks at each pair of points (pi, pj) at most twice: once when adding pi to the tour, the other when adding pj

I can't figure out the scenario in which a particular (pi, pj) pair is considered more than once, since each step only considers points that haven't been visited yet.
When you're at pi, if you haven't yet visited pj you'll consider (pi, pj). But once you've left pi, when would you ever consider another pair that includes it?
Is the author referring to the case where pi is the first point visited and pj is the last before returning to complete the circuit? If so, does that really qualify as a case where the pair of points needs any consideration, since we have no choice but to return to the starting position since all the points in the set have been visited?
 A: Skiena only gives an outline sketch of the problem and the algorithm:

Input: A set $S$ of $n$ points in the plane
NearestNeighbour($P$)
          Pick and visit an initial point $p_0$ from $P$
          $i = 0$
          While there are still unvisited points
                  $i = i + 1$
                  Select $p_i$ to be the closest unvisited point to $p_{i-1}$
                  Visit $p_i$
          Return to $p_0$ from $p_{n-1}$

so we can't be sure how any of these steps are implemented: it depends crucially on the data structure that is used to represent the set of visited points. Here are two possible implementation strategies:


*

*We maintain a map $v: S → {0,1}$ such that $v(p)=1$ if $p$ has been visited, and $v(p)=0$ otherwise. Initially $v(p)=0$ for all $p∈S$.
To implement the step "Select $p_i$ to be the closest unvisited point to $p_{i-1}$" we loop over $q∈S$ and if $v(q)=0$, then we consider $q$ as a candidate for $p_i$.
To implement the step "Visit $p_i$" we set $v(p_i)=1$.

*We maintain a set $U ⊆ S$ of unvisited points. Initially $U = S$.
To implement the step "Select $p_i$ to be the closest unvisited point to $p_{i-1}$" we loop over all $q∈U$ and consider them as candidates for $p_i$.
To implement the step "Visit $p_i$" we remove $p_i$ from $U$.
It looks as though Skiena is thinking of an implementation like (1), in which the loop goes over all points, including ones that have been visited before, and you are thinking of an implementation like (2), in which the loop only considers the unvisited points.
The reason for thinking in terms of an implementation like (1) is that it's conceptually simple (the map $v$ can be implemented as an array of bits). Whereas an implementation like (2) needs a "set" data structure with $O(n)$ traversal and $O(1)$ deletion, and it is not immediately obvious at this point in the book how to implement such a data structure. The example is from §1.1 and Skiena doesn't consider data structures that could be used for efficient set implementations until §3 (doubly-linked lists) and §6 (hash tables).
