4
$\begingroup$

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.

2 Answers 2

3

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.

  • 0
    @Lieven : OK, I now see wh$a$t 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.2012-08-14
2

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.

  • 0
    Can you generalize this to the second nearest neighbor? Nobody has answered the third case yet.2012-08-14