Question about proof of Manhattan Minimal Spanning Tree

402 Views Asked by At

In this tutorial about line sweep algorithms, there is a section for minimal spanning tree. There is a part that says:-

The figure shows the situation in just one of the octants, the West-Northwest one. Q is the closest neighbour (with the dashed line indicating points at the same Manhattan distance as Q), and R is some other point in the octant. If PR is an edge in a spanning tree, then it can be removed and replaced by either PQ or QR to produce a better spanning tree, because the shape of the octant guarantees that |QR| = |PR|.

This is the figure:- figure

How do we prove the claim |QR| = |PR| (Also I think it might be a typo and the actual claim be |QR| <= |PR|)? And why do we have to consider octants, and not quadrants for this. It intuitively seems to make sense, but what is the reasoning behind it?