<ul class="metadata page-metadata" data-bi-name="page info" lang="en-us" dir="ltr">

Last update:

<h2 id="manhattan-minimum-spanning-tree">Manhattan Minimum Spanning Tree<a class="headerlink" href="#manhattan-minimum-spanning-tree" title="Permanent link">&para;</a></h2>

<p>The Manhattan MST problem consists of, given some points in the plane, find the edges that connect all the points and have a minimum total sum of weights. The weight of an edge that connects two points is their Manhattan distance. For simplicity, we assume that all points have different locations.

Here we show a way of finding the MST in <span class="arithmatex">$O(n \log{n})$</span> by finding for each point its nearest neighbor in each octant, as represented by the image below. This will give us <span class="arithmatex">$O(n)$</span> candidate edges, which, as we show below, will guarantee that they contain the MST. The final step is then using some standard MST, for example, <a href="https://cp-algorithms.com/graph/mst_kruskal_with_dsu.html">Kruskal algorithm using disjoint set union</a>.</p>

<p>The algorithm shown here was first presented in a paper from <a href="https://ieeexplore.ieee.org/document/913303">H. Zhou, N. Shenoy, and W. Nichollos (2002)</a>. There is also another know algorithm that uses a Divide and conquer approach by <a href="https://www.academia.edu/15667173/On_computing_all_north_east_nearest_neighbors_in_the_L1_metric">J. Stolfi</a>, which is also very interesting and only differ in the way they find the nearest neighbor in each octant. They both have the same complexity, but the one presented here is easier to implement and has a lower constant factor.</p>

<p>First, let's understand why it is enough to consider only the nearest neighbor in each octant. The idea is to show that for a point <span class="arithmatex">$s$</span> and any two other points <span class="arithmatex">$p$</span> and <span class="arithmatex">$q$</span> in the same octant, <span class="arithmatex">$d(p, q) &lt; \max(d(s, p), d(s, q))$</span>. This is important, because it shows that if there was a MST where <span class="arithmatex">$s$</span> is connected to both <span class="arithmatex">$p$</span> and <span class="arithmatex">$q$</span>, we could erase one of these edges and add the edge <span class="arithmatex">$(p,q)$</span>, which would decrease the total cost. To prove this, we assume without loss of generality that <span class="arithmatex">$p$</span> and <span class="arithmatex">$q$</span> are in the octanct <span class="arithmatex">$R_1$</span>, which is defined by: <span class="arithmatex">$x_s \leq x$</span> and <span class="arithmatex">$x_s - y_s &gt; x - y$</span>, and then do some casework. The image below give some intuition on why this is true.</p>

<p>Therefore, the main question is how to find the nearest neighbor in each octant for every single of the <span class="arithmatex">$n$</span> points.</p>

<h2 id="nearest-neighbor-in-each-octant-in-on-log-n">Nearest Neighbor in each Octant in O(n log n)<a class="headerlink" href="#nearest-neighbor-in-each-octant-in-on-log-n" title="Permanent link">&para;</a></h2>

<p>For simplicity we focus on the NNE octant (<span class="arithmatex">$R_1$</span> in the image above). All other directions can be found with the same algorithm by rotating the input.</p>

<p>We will use a sweep-line approach. We process the points from south-west to north-east, that is, by non-decreasing <span class="arithmatex">$x + y$</span>. We also keep a set of points which don't have their nearest neighbor yet, which we call "active set". We add the images below to help visualize the algorithm.</p>

<p>When we add a new point point <span class="arithmatex">$p$</span>, for every point <span class="arithmatex">$s$</span> that has it in its octant we can safely assign <span class="arithmatex">$p$</span> as the nearest neighbor. This is true because their distance is <span class="arithmatex">$d(p,s) = |x_p - x_s| + |y_p - y_s| = (x_p + y_p) - (x_s + y_s)$</span>, because <span class="arithmatex">$p$</span> is in the north-north-east octant. As all the next points will not have a smaller value of <span class="arithmatex">$x + y$</span> because of the sorting step, <span class="arithmatex">$p$</span> is guaranteed to have the smaller distance. We can then remove all such points from the active set, and finally add <span class="arithmatex">$p$</span> to the active set.</p>

<p>The next question is how to efficiently find which points <span class="arithmatex">$s$</span> have <span class="arithmatex">$p$</span> in the north-north-east octant. That is, which points <span class="arithmatex">$s$</span> satisfy:</p>

<ul class="metadata page-metadata" data-bi-name="page info" lang="en-us" dir="ltr">

<span class="contributors-text">Contributors:</span>

</article>

<ul class="metadata page-metadata" data-bi-name="page info" lang="en-us" dir="ltr">

Last update:

<p>We can find the path <span class="arithmatex">$s - A - B - t$</span> with the residual capacities 7, 5, and 8.

Their minimum is 5, therefore we can increase the flow along this path by 5.

This gives a flow of 5 for the network.</p>

<p>Again we look for an augmenting path, this time we find <span class="arithmatex">$s - D - A - C - t$</span> with the residual capacities 4, 3, 3, and 5.

Therefore we can increase the flow by 3 and we get a flow of 8 for the network.</p>

<p>This time we find the path <span class="arithmatex">$s - D - C - B - t$</span> with the residual capacities 1, 2, 3, and 3, and hence, we increase the flow by 1.</p>

<p>This time we find the augmenting path <span class="arithmatex">$s - A - D - C - t$</span> with the residual capacities 2, 3, 1, and 2.

We can increase the flow by 1.

But because we already have a flow of 3 from <span class="arithmatex">$D$</span> to <span class="arithmatex">$A$</span>, this is possible.

The intuition of it is the following:

Instead of sending a flow of 3 from <span class="arithmatex">$D$</span> to <span class="arithmatex">$A$</span>, we only send 2 and compensate this by sending an additional flow of 1 from <span class="arithmatex">$s$</span> to <span class="arithmatex">$A$</span>, which allows us to send an additional flow of 1 along the path <span class="arithmatex">$D - C - t$</span>.</p>

<p>Now, it is impossible to find an augmenting path between <span class="arithmatex">$s$</span> and <span class="arithmatex">$t$</span>, therefore this flow of <span class="arithmatex">$10$</span> is the maximal possible.

We have found the maximal flow.</p>

<ul class="metadata page-metadata" data-bi-name="page info" lang="en-us" dir="ltr">

<span class="contributors-text">Contributors:</span>

</article>