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

Last update:

<spanclass="git-revision-date-localized-plugin git-revision-date-localized-plugin-date"title="April15, 2025 02:32:08">April15, 2025</span>&emsp;

<spanclass="git-revision-date-localized-plugin git-revision-date-localized-plugin-date"title="April22, 2025 02:11:52">April22, 2025</span>&emsp;

<h2id="manhattan-minimum-spanning-tree">Manhattan Minimum Spanning Tree<aclass="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<spanclass="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<spanclass="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,<ahref="https://cp-algorithms.com/graph/mst_kruskal_with_dsu.html">Kruskal algorithm using disjoint set union</a>.</p>

<center>

*The 8 octants relative to a point S*</center>

<divstyle="text-align: center;">

<imgsrc="manhattan-mst-octants.png"alt="8 octants picture">

*The 8 octants relative to a point S*

<p>The algorithm shown here was first presented in a paper from<ahref="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<ahref="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<spanclass="arithmatex">$s$</span> and any two other points<spanclass="arithmatex">$p$</span> and<spanclass="arithmatex">$q$</span> in the same octant,<spanclass="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<spanclass="arithmatex">$s$</span> is connected to both<spanclass="arithmatex">$p$</span> and<spanclass="arithmatex">$q$</span>, we could erase one of these edges and add the edge<spanclass="arithmatex">$(p,q)$</span>, which would decrease the total cost. To prove this, we assume without loss of generality that<spanclass="arithmatex">$p$</span> and<spanclass="arithmatex">$q$</span> are in the octanct<spanclass="arithmatex">$R_1$</span>, which is defined by:<spanclass="arithmatex">$x_s \leq x$</span> and<spanclass="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>

<center>

*Intuitively, the limitation of the octant makes it impossible that $p$ and $q$ are both closer to $s$ than to each other*</center>

<divstyle="text-align: center;">

<imgsrc="manhattan-mst-uniqueness.png"alt="unique nearest neighbor">

*Intuitively, the limitation of the octant makes it impossible that $p$ and $q$ are both closer to $s$ than to each other*

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

<h2id="nearest-neighbor-in-each-octant-in-on-log-n">Nearest Neighbor in each Octant in O(n log n)<aclass="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 (<spanclass="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<spanclass="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>

<center>

*In black with an arrow you can see the direction of the line-sweep. All the points below this lines are in the active set, and the points above are still not processed. In green we see the points which are in the octant of the processed point. In red the points that are not in the searched octant.*</center>

<center>

<divstyle="text-align: center;">

<imgsrc="manhattan-mst-sweep-line-1.png"alt="manhattan-mst-sweep">

*In black with an arrow you can see the direction of the line-sweep. All the points below this lines are in the active set, and the points above are still not processed. In green we see the points which are in the octant of the processed point. In red the points that are not in the searched octant.*

*In this image we see the active set after processing the point $p$. Note that the $2$ green points of the previous image had $p$ in its north-north-east octant and are not in the active set anymore, because they already found their nearest neighbor.*</center>

<divstyle="text-align: center;">

<imgsrc="manhattan-mst-sweep-line-2.png"alt="manhattan-mst-sweep">

*In this image we see the active set after processing the point $p$. Note that the $2$ green points of the previous image had $p$ in its north-north-east octant and are not in the active set anymore, because they already found their nearest neighbor.*

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

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

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

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

<ulclass="contributors"data-bi-name="contributors"><li><ahref="https://github.com/NaimSS"title="NaimSS"data-bi-name="contributorprofile"target="_blank">NaimSS</a> (80.0%)</li><li><ahref="https://github.com/gabsrp2002"title="gabsrp2002"data-bi-name="contributorprofile"target="_blank">gabsrp2002</a> (11.89%)</li><li><ahref="https://github.com/izanbf1803"title="izanbf1803"data-bi-name="contributorprofile"target="_blank">izanbf1803</a> (3.78%)</li><li><ahref="https://github.com/mhayter"title="mhayter"data-bi-name="contributorprofile"target="_blank">mhayter</a> (3.24%)</li><li><ahref="https://github.com/adamant-pwn"title="adamant-pwn"data-bi-name="contributorprofile"target="_blank">adamant-pwn</a> (1.08%)</li></ul>

<ulclass="contributors"data-bi-name="contributors"><li><ahref="https://github.com/NaimSS"title="NaimSS"data-bi-name="contributorprofile"target="_blank">NaimSS</a> (71.95%)</li><li><ahref="https://github.com/mhayter"title="mhayter"data-bi-name="contributorprofile"target="_blank">mhayter</a> (11.64%)</li><li><ahref="https://github.com/gabsrp2002"title="gabsrp2002"data-bi-name="contributorprofile"target="_blank">gabsrp2002</a> (11.64%)</li><li><ahref="https://github.com/izanbf1803"title="izanbf1803"data-bi-name="contributorprofile"target="_blank">izanbf1803</a> (3.7%)</li><li><ahref="https://github.com/adamant-pwn"title="adamant-pwn"data-bi-name="contributorprofile"target="_blank">adamant-pwn</a> (1.06%)</li></ul>

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

Last update:

<spanclass="git-revision-date-localized-plugin git-revision-date-localized-plugin-date"title="April15, 2025 02:32:08">April15, 2025</span>&emsp;

<spanclass="git-revision-date-localized-plugin git-revision-date-localized-plugin-date"title="April22, 2025 02:45:52">April22, 2025</span>&emsp;

<p>We can find the path<spanclass="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>

<center> </center>

<divstyle="text-align: center;">

<imgsrc="Flow2.png"alt="First path">

<imgsrc="Flow3.png"alt="Network after first path">

<p>Again we look for an augmenting path, this time we find<spanclass="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>

<center> </center>

<divstyle="text-align: center;">

<imgsrc="Flow4.png"alt="Second path">

<imgsrc="Flow5.png"alt="Network after second path">

<p>This time we find the path<spanclass="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>

<center> </center>

<divstyle="text-align: center;">

<imgsrc="Flow6.png"alt="Third path">

<imgsrc="Flow7.png"alt="Network after third path">

<p>This time we find the augmenting path<spanclass="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<spanclass="arithmatex">$D$</span> to<spanclass="arithmatex">$A$</span>, this is possible.

The intuition of it is the following:

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

<center> </center>

<divstyle="text-align: center;">

<imgsrc="Flow8.png"alt="Fourth path">

<imgsrc="Flow9.png"alt="Network after fourth path">

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

We have found the maximal flow.</p>

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

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

<ulclass="contributors"data-bi-name="contributors"><li><ahref="https://github.com/jakobkogler"title="jakobkogler"data-bi-name="contributorprofile"target="_blank">jakobkogler</a> (70.98%)</li><li><ahref="https://github.com/DamianArado"title="DamianArado"data-bi-name="contributorprofile"target="_blank">DamianArado</a> (12.05%)</li><li><ahref="https://github.com/mhayter"title="mhayter"data-bi-name="contributorprofile"target="_blank">mhayter</a> (5.36%)</li><li><ahref="https://github.com/adamant-pwn"title="adamant-pwn"data-bi-name="contributorprofile"target="_blank">adamant-pwn</a> (3.1300000000000003%)</li><li><ahref="https://github.com/infalmo"title="infalmo"data-bi-name="contributorprofile"target="_blank">infalmo</a> (1.79%)</li><li><ahref="https://github.com/LUTLJS"title="LUTLJS"data-bi-name="contributorprofile"target="_blank">LUTLJS</a> (1.34%)</li><li><ahref="https://github.com/Aryamn"title="Aryamn"data-bi-name="contributorprofile"target="_blank">Aryamn</a> (1.34%)</li><li><ahref="https://github.com/Kakalinn"title="Kakalinn"data-bi-name="contributorprofile"target="_blank">Kakalinn</a> (0.89%)</li><li><ahref="https://github.com/kd1729"title="kd1729"data-bi-name="contributorprofile"target="_blank">kd1729</a> (0.45%)</li><li><ahref="https://github.com/obiwac"title="obiwac"data-bi-name="contributorprofile"target="_blank">obiwac</a> (0.45%)</li><li><ahref="https://github.com/shivensinha4"title="shivensinha4"data-bi-name="contributorprofile"target="_blank">shivensinha4</a> (0.45%)</li><li><ahref="https://github.com/lm10-piyush"title="lm10-piyush"data-bi-name="contributorprofile"target="_blank">lm10-piyush</a> (0.45%)</li><li><ahref="https://github.com/ShayekhBinIslam"title="ShayekhBinIslam"data-bi-name="contributorprofile"target="_blank">ShayekhBinIslam</a> (0.45%)</li><li><ahref="https://github.com/wikku"title="wikku"data-bi-name="contributorprofile"target="_blank">wikku</a> (0.45%)</li><li><ahref="https://github.com/roll-no-1"title="roll-no-1"data-bi-name="contributorprofile"target="_blank">roll-no-1</a> (0.45%)</li></ul>

<ulclass="contributors"data-bi-name="contributors"><li><ahref="https://github.com/jakobkogler"title="jakobkogler"data-bi-name="contributorprofile"target="_blank">jakobkogler</a> (65.68%)</li><li><ahref="https://github.com/mhayter"title="mhayter"data-bi-name="contributorprofile"target="_blank">mhayter</a> (11.86%)</li><li><ahref="https://github.com/DamianArado"title="DamianArado"data-bi-name="contributorprofile"target="_blank">DamianArado</a> (11.44%)</li><li><ahref="https://github.com/adamant-pwn"title="adamant-pwn"data-bi-name="contributorprofile"target="_blank">adamant-pwn</a> (2.96%)</li><li><ahref="https://github.com/infalmo"title="infalmo"data-bi-name="contributorprofile"target="_blank">infalmo</a> (1.69%)</li><li><ahref="https://github.com/LUTLJS"title="LUTLJS"data-bi-name="contributorprofile"target="_blank">LUTLJS</a> (1.27%)</li><li><ahref="https://github.com/Aryamn"title="Aryamn"data-bi-name="contributorprofile"target="_blank">Aryamn</a> (1.27%)</li><li><ahref="https://github.com/Kakalinn"title="Kakalinn"data-bi-name="contributorprofile"target="_blank">Kakalinn</a> (0.85%)</li><li><ahref="https://github.com/kd1729"title="kd1729"data-bi-name="contributorprofile"target="_blank">kd1729</a> (0.42%)</li><li><ahref="https://github.com/obiwac"title="obiwac"data-bi-name="contributorprofile"target="_blank">obiwac</a> (0.42%)</li><li><ahref="https://github.com/shivensinha4"title="shivensinha4"data-bi-name="contributorprofile"target="_blank">shivensinha4</a> (0.42%)</li><li><ahref="https://github.com/lm10-piyush"title="lm10-piyush"data-bi-name="contributorprofile"target="_blank">lm10-piyush</a> (0.42%)</li><li><ahref="https://github.com/ShayekhBinIslam"title="ShayekhBinIslam"data-bi-name="contributorprofile"target="_blank">ShayekhBinIslam</a> (0.42%)</li><li><ahref="https://github.com/wikku"title="wikku"data-bi-name="contributorprofile"target="_blank">wikku</a> (0.42%)</li><li><ahref="https://github.com/roll-no-1"title="roll-no-1"data-bi-name="contributorprofile"target="_blank">roll-no-1</a> (0.42%)</li></ul>