# Can lines connecting nearest neighbors ever cross?

I don't have any background in graph theory so I am sorry if this is a basic question. I want to know if lines connecting nearest neighbors can cross in a few different cases.

• I have convinced myself that if there are no ties for nearest neighbor it is impossible for lines to cross. Is this correct?
• I think it might still be impossible even if ties are allowed, in which case either or both lines can be drawn but I haven't come up with solid reasoning to back that up.
• This case is a bit more complicated. Say that points can be connected to their second nearest neighbor if a line originating from them has yet to be drawn and they are already connected to their nearest neighbor. In this condition, two pairs of points very far from one another would be connected into one long line. Each pair would get a line connecting it to its nearest neighbor and then one or two lines would connect between the pairs. Connecting to the third nearest neighbor is not allowed. It seems to me that in this case as well no lines would cross.

I have no idea where to begin looking for formal math to back up these statements. Is there a general theory of lines crossing in a network of nearest neighbor connections? Any help would be appreciated.

-

If $A$ has nearest neighbor $B$, then any point $x$ on the line segment joining $A$ and $B$ is nearest to either $A$ or $B$, but not to any other point (not even tied):

Assume that there exists a point $C$, such that $d(x,C) \leq d(x,A),d(x,B)$ for some $x$ on $AB$. Then, by the triangle inequality (the inequality is strict because we know $C$ can't lie on $AB$)

\begin{align*} d(A,C) &< d(A,x) + d(x,C) \\ &< d(A,x) + d(x,B) \\ &< d(A,B) \end{align*}

contradicting the fact that $B$ is the nearest neighbor of $A$.

Now assume there are 4 points $A,B,C,D$, such that there's an edge between $A,B$ and between $C,D$. Then if the lines $AB$ and $CD$ would cross, the point of intersection $x$ would be strictly nearer to at least one of $A$, $B$ than to any other point, and also strictly nearer to at least one of $C,D$ than to any other point, which is absurd.

Also, for some general theory: Voronoi diagrams and Delaunay triangulations can be very helpful when thinking about such problems. The above is actually equivalent to the fact that in a Voronoi diagram, the line connecting two nearest neighbors only crosses the Voronoi cells of these two points (which must be adjacent).

EDIT: I overlooked something: If $A$ is the point nearest to $B$, then that doesn't necessarily imply that $B$ is also the nearest point to $A$. I assume you want to consider the graph formed by connecting every point to its nearest neighbor (so it can happen that multiple lines are adjacent to a certain point). The argument was easy to fix though.

-
thank you. Does your argument generalize to connecting points to their nearest and second nearest neighbor? I know lines start crossing if points connect to their third nearest neighbor but it still seems to me there should be a way to show that no crossings can happen for second nearest. – Hammer Aug 14 '12 at 18:27
There is an error here: "the line connecting two nearest neighbors only crosses the Voronoi cells of these two points". That's not true. If $B=(10,0)$, $C=(9,-1)$, and $A=(0,0)$, then the line segment from $A$ to $B$ passes through the Voronoi cell of $C$ (assuming no other points than $A$, $B$, $C$ are considered). Draw the picture and you'll see it. In particular, the point $(8,0)$ is in the Voronoi cell of $C$. – Michael Hardy Aug 14 '12 at 20:13
but $9^2 + (-1)^2 = 82 < 10^2 = 100$, so the nearest neighbor to $A$ is in fact $C$. – Lieven Aug 14 '12 at 20:18
The fact that two sites have neighboring Voronoi cells doesn't mean at least one of them is the nearest neighbor of the other. Take $A,B,C$ as in my comment above. The nearest neighbor of $A$ is $C$; the nearest neighbor of $B$ is $C$; the nearest neighbor of $C$ is $B$. So neither $A$ nor $B$ is the other's nearest neighbor. But (as always happens in a Voronoi diagram in the plane with only three non-collinear sites) $A$ and $B$ have neighboring Voronoi cells. – Michael Hardy Aug 14 '12 at 20:20
@Lieven : OK, I now see what you're saying. At first I thought you were saying the line between two neighboring points in a Voronoi diagram only passes through their two Voronoi cells. – Michael Hardy Aug 14 '12 at 20:20

Assume $A,B,C,D$ are distinct points, $B$ is the closest to $A$ of $B,C,D$, and $D$ is the closest to $C$ of $A,B,D$ (with possible ties). Suppose the lines $AB$ and $CD$ cross at $E$. If $E$ is $A$ or $B$, it is closer to $C$ than $D$ is, contradicting the assumption that $D$ is the closest to $C$. Similarly if $E$ is $C$ or $D$, it is closer to $A$ than $B$ is. The remaining case is where $E$ is distinct from $A,B,C,D$. Then $d(A,D) < d(A,E) + d(E,D)$ and $d(B,C) < d(B,E) + d(E,C)$ so $d(A,D) + d(B,C) < d(A,E)+d(E,B) + d(C,E)+d(E,D) = d(A,B)+d(C,D)$. But by assumption $d(A,B) \le d(A,D)$ and $d(C,D) \le d(B,C)$ so $d(A,B) + d(C,D) \le d(A,D)+d(B,C)$, contradiction.

-
Can you generalize this to the second nearest neighbor? Nobody has answered the third case yet. – Hammer Aug 14 '12 at 21:33