Euclidean minimum spanning tree

<h2 id="definition-and-related-problems">Definition and related problems</h2>
A Euclidean minimum spanning tree, for a set of 
 
 
 
 n
 
 
 {\displaystyle n}
 
 points in the <a href="/facts/Euclidean_plane/tAUtRFcn">Euclidean plane</a> or <a href="/facts/Euclidean_space/R2UbzmzM">Euclidean space</a>, is a system of <a href="/facts/Line_segment/V8E0M4qk">line segments</a>, having only the given points as their endpoints, whose union includes all of the points in a <a href="/facts/Connected_set/5CUTxfoA">connected set</a>, and which has the minimum possible total length of any such system. Such a network cannot contain a <a href="/facts/Polygon/yAq7RjPz">polygonal</a> ring of segments; if one existed, the network could be shortened by removing an edge of the polygon. Therefore, the minimum-length network forms a <a href="/facts/Tree_(graph_theory)/TCWk4Joy">tree</a>. This observation leads to the equivalent definition that a Euclidean minimum spanning tree is a tree of line segments between pairs of the given points, of minimum total length.<a class="footnote-ref" id="fnref:1" href="#fn:1">1</a> The same tree may also be described as a <a href="/facts/Minimum_spanning_tree/kgkGmY9s">minimum spanning tree</a> of a weighted <a href="/facts/Complete_graph/AYD6hUqI">complete graph</a>, having the given points as its vertices and the distances between points as edge weights.<a class="footnote-ref" id="fnref:2" href="#fn:2">2</a> The same points may have more than one minimum spanning tree. For instance, for the vertices of a <a href="/facts/Regular_polygon/ws89Nhpt">regular polygon</a>, removing any edge of the polygon produces a minimum spanning tree.<a class="footnote-ref" id="fnref:3" href="#fn:3">3</a>
Publications on the Euclidean minimum spanning tree commonly abbreviate it as "EMST".<a class="footnote-ref" id="fnref:4" href="#fn:4">4</a><a class="footnote-ref" id="fnref:5" href="#fn:5">5</a> They may also be called "geometric minimum spanning trees",<a class="footnote-ref" id="fnref:6" href="#fn:6">6</a><a class="footnote-ref" id="fnref:7" href="#fn:7">7</a> but that term may be used more generally for geometric spaces with non-Euclidean distances, such as <a href="/facts/Lp_space/gbad0Rv1">Lp spaces</a>.<a class="footnote-ref" id="fnref:8" href="#fn:8">8</a> When the context of Euclidean point sets is clear, they may be called simply "minimum spanning trees".<a class="footnote-ref" id="fnref:9" href="#fn:9">9</a><a class="footnote-ref" id="fnref:10" href="#fn:10">10</a><a class="footnote-ref" id="fnref:11" href="#fn:11">11</a>
Several other standard geometric networks are closely related to the Euclidean minimum spanning tree:

<ul><li>The <a href="/facts/Steiner_tree_problem/5mhCq8cN">Steiner tree problem</a> again seeks a system of line segments connecting all given points, but without requiring the segments to start and end only at given points. In this problem, additional points may be added as segment endpoints, allowing the Steiner tree to be shorter than the minimum spanning tree.<a class="footnote-ref" id="fnref:12" href="#fn:12">12</a></li>
<li>In the Euclidean <a href="/facts/Travelling_salesman_problem/2WEKVLnV">traveling salesperson path problem</a>, the connecting line segments must start and end at the given points, like the spanning tree and unlike the Steiner tree; additionally, each point can touch at most two line segments, so the result forms a <a href="/facts/Polygonal_chain/GRQ6BMQS">polygonal chain</a>. Because of this restriction, the optimal path may be longer than the Euclidean minimum spanning tree, but is at most twice as long.<a class="footnote-ref" id="fnref:13" href="#fn:13">13</a></li>
<li><a href="/facts/Geometric_spanner/yblwj8bF">Geometric spanners</a> are low-weight networks that, like the minimum spanning tree, connect all of the points. Unlike the minimum spanning tree, all of these connecting paths are required to be short, having length proportional to the distance between the points they connect. To achieve this property, these networks generally have cycles and so are not trees.<a class="footnote-ref" id="fnref:14" href="#fn:14">14</a></li></ul>
<h2 id="properties">Properties</h2>
<h3>Angles and vertex degrees</h3>

Whenever two edges of a Euclidean minimum spanning tree meet at a vertex, they must form an angle of 60° or more, with equality only when they form two sides of an <a href="/facts/Equilateral_triangle/MJomsYDS">equilateral triangle</a>. This is because, for two edges forming any sharper angle, one of the two edges could be replaced by the third, shorter edge of the triangle they form, forming a tree with smaller total length.<a class="footnote-ref" id="fnref:15" href="#fn:15">15</a> In comparison, the Steiner tree problem has a stronger angle bound: an optimal Steiner tree has all angles at least 120°.<a class="footnote-ref" id="fnref:16" href="#fn:16">16</a>
The same 60° angle bound also occurs in the <a href="/facts/Kissing_number/UE3mtV0d">kissing number</a> problem, of finding the maximum number of <a href="/facts/Unit_sphere/5UeoTcug">unit spheres</a> in Euclidean space that can be tangent to a central unit sphere without any two spheres intersecting (beyond a point of tangency). The center points of these spheres have a minimum spanning tree in the form of a <a href="/facts/Star_(graph_theory)/PNW0H6eK">star</a>, with the central point adjacent to all other points. Conversely, for any vertex 
 
 
 
 v
 
 
 {\displaystyle v}
 
 of any minimum spanning tree, one can construct non-overlapping unit spheres centered at 
 
 
 
 v
 
 
 {\displaystyle v}
 
 and at points two units along each of its edges, with a tangency for each neighbor of 
 
 
 
 v
 
 
 {\displaystyle v}
 
. Therefore, in 
 
 
 
 n
 
 
 {\displaystyle n}
 
-dimensional space the maximum possible <a href="/facts/Degree_(graph_theory)/LnFFpI8v">degree</a> of a vertex (the number of spanning tree edges connected to it) equals the kissing number of spheres in 
 
 
 
 n
 
 
 {\displaystyle n}
 
 dimensions.<a class="footnote-ref" id="fnref:17" href="#fn:17">17</a> Planar minimum spanning trees have degree at most six, and when a tree has degree six there is always another minimum spanning tree with maximum degree five.<a class="footnote-ref" id="fnref:18" href="#fn:18">18</a> Three-dimensional minimum spanning trees have degree at most twelve.<a class="footnote-ref" id="fnref:19" href="#fn:19">19</a> The only higher dimensions in which the exact value of the kissing number is known are four, eight, and 24 dimensions.<a class="footnote-ref" id="fnref:20" href="#fn:20">20</a>
For points generated at random from a given continuous distribution, the minimum spanning tree is <a href="/facts/Almost_surely/fWaxzpBA">almost surely</a> unique. The numbers of vertices of any given degree converge, for large number of vertices, to a constant times that number of vertices. The values of these constants depend on the degree and the distribution. However, even for simple cases—such as the number of leaves for points uniformly distributed in a unit square—their precise values are not known.<a class="footnote-ref" id="fnref:21" href="#fn:21">21</a>

<h3>Empty regions</h3>

For any edge 
 
 
 
 u
 v
 
 
 {\displaystyle uv}
 
 of any Euclidean minimum spanning tree, the <a href="/facts/Lens_(geometry)/mpgyWrWz">lens</a> (or <a href="/facts/Vesica_piscis/et7eCVQH">vesica piscis</a>) formed by intersecting the two circles with 
 
 
 
 u
 v
 
 
 {\displaystyle uv}
 
 as their radii cannot have any other given vertex 
 
 
 
 w
 
 
 {\displaystyle w}
 
 in its interior. Put another way, if any tree has an edge 
 
 
 
 u
 v
 
 
 {\displaystyle uv}
 
 whose lens contains a third point 
 
 
 
 w
 
 
 {\displaystyle w}
 
, then it is not of minimum length. For, by the geometry of the two circles, 
 
 
 
 w
 
 
 {\displaystyle w}
 
 would be closer to both 
 
 
 
 u
 
 
 {\displaystyle u}
 
 and 
 
 
 
 v
 
 
 {\displaystyle v}
 
 than they are to each other. If edge 
 
 
 
 u
 v
 
 
 {\displaystyle uv}
 
 were removed from the tree, 
 
 
 
 w
 
 
 {\displaystyle w}
 
 would remain connected to one of 
 
 
 
 u
 
 
 {\displaystyle u}
 
 and 
 
 
 
 v
 
 
 {\displaystyle v}
 
, but not the other. Replacing the removed edge 
 
 
 
 u
 v
 
 
 {\displaystyle uv}
 
 by 
 
 
 
 u
 w
 
 
 {\displaystyle uw}
 
 or 
 
 
 
 v
 w
 
 
 {\displaystyle vw}
 
 (whichever of these two edges reconnects 
 
 
 
 w
 
 
 {\displaystyle w}
 
 to the vertex from which it was disconnected) would produce a shorter tree.<a class="footnote-ref" id="fnref:22" href="#fn:22">22</a>
For any edge 
 
 
 
 u
 v
 
 
 {\displaystyle uv}
 
 of any Euclidean minimum spanning tree, the <a href="/facts/Rhombus/T4pU50GF">rhombus</a> with angles of 60° and 120°, having 
 
 
 
 u
 v
 
 
 {\displaystyle uv}
 
 as its long diagonal, is disjoint from the rhombi formed analogously by all other edges. Two edges sharing an endpoint cannot have overlapping rhombi, because that would imply an edge angle sharper than 60°, and two disjoint edges cannot have overlapping rhombi; if they did, the longer of the two edges could be replaced by a shorter edge among the same four vertices.<a class="footnote-ref" id="fnref:23" href="#fn:23">23</a>

<h3>Supergraphs</h3>
Certain <a href="/facts/Geometric_graph/4vIAySX3">geometric graphs</a> have definitions involving empty regions in point sets, from which it follows that they contain every edge that can be part of a Euclidean minimum spanning tree. These include:

<ul><li>The <a href="/facts/Relative_neighborhood_graph/8PUNYtWy">relative neighborhood graph</a>, which has an edge between any pair of points whenever the lens they define is empty.</li>
<li>The <a href="/facts/Gabriel_graph/UYIRYo52">Gabriel graph</a>, which has an edge between any pair of points whenever the circle having the pair as a diameter is empty.</li>
<li>The <a href="/facts/Delaunay_triangulation/6VRk7cS9">Delaunay triangulation</a>, which has an edge between any pair of points whenever there exists an empty circle having the pair as a chord.</li>
<li>The <a href="/facts/Urquhart_graph/QU4Lgd2a">Urquhart graph</a>, formed from the Delaunay triangulation by removing the longest edge of each triangle. For each remaining edge, the vertices of the Delaunay triangles that use that edge cannot lie within the empty lune of the relative neighborhood graph.</li></ul>
Because the empty-region criteria for these graphs are progressively weaker, these graphs form an ordered sequence of subgraphs. That is, using "⊆" to denote the subset relationship among their edges, these graphs have the relations:

Euclidean minimum spanning tree ⊆ relative neighborhood graph ⊆ Urquhart graph ⊆ Gabriel graph ⊆ Delaunay triangulation.<a class="footnote-ref" id="fnref:24" href="#fn:24">24</a><a class="footnote-ref" id="fnref:25" href="#fn:25">25</a>
Another graph guaranteed to contain the minimum spanning tree is the <a href="/facts/Yao_graph/pdu3o4Dk">Yao graph</a>, determined for points in the plane by dividing the plane around each point into six 60° wedges and connecting each point to the nearest neighbor in each wedge. The resulting graph contains the relative neighborhood graph, because two vertices with an empty lens must be the nearest neighbors to each other in their wedges. As with many of the other geometric graphs above, this definition can be generalized to higher dimensions, and (unlike the Delaunay triangulation) its generalizations always include a linear number of edges.<a class="footnote-ref" id="fnref:26" href="#fn:26">26</a><a class="footnote-ref" id="fnref:27" href="#fn:27">27</a>

<h3>Total length</h3>
For 
 
 
 
 n
 
 
 {\displaystyle n}
 
 points in the <a href="/facts/Unit_square/6aJUASbv">unit square</a> (or any other fixed shape), the total length of the minimum spanning tree edges is 
 
 
 
 O
 (
 
 
 n
 
 
 )
 
 
 {\displaystyle O({\sqrt {n}})}
 
. Some sets of points, such as points evenly spaced in a 
 
 
 
 
 
 n
 
 
 ×
 
 
 n
 
 
 
 
 {\displaystyle {\sqrt {n}}\times {\sqrt {n}}}
 
 grid, attain this bound.<a class="footnote-ref" id="fnref:28" href="#fn:28">28</a> For points in a unit hypercube in 
 
 
 
 d
 
 
 {\displaystyle d}
 
-dimensional space, the corresponding bound is 
 
 
 
 O
 (
 
 n
 
 (
 d
 −
 1
 )
 
 /
 
 d
 
 
 )
 
 
 {\displaystyle O(n^{(d-1)/d})}
 
.<a class="footnote-ref" id="fnref:29" href="#fn:29">29</a> The same bound applies to the expected total length of the minimum spanning tree for 
 
 
 
 n
 
 
 {\displaystyle n}
 
 points chosen uniformly and independently from a unit square or unit hypercube.<a class="footnote-ref" id="fnref:30" href="#fn:30">30</a> Returning to the unit square, the sum of squared edge lengths of the minimum spanning tree is 
 
 
 
 O
 (
 1
 )
 
 
 {\displaystyle O(1)}
 
. This bound follows from the observation that the edges have disjoint rhombi, with area proportional to the edge lengths squared. The 
 
 
 
 O
 (
 
 
 n
 
 
 )
 
 
 {\displaystyle O({\sqrt {n}})}
 
 bound on total length follows by application of the <a href="/facts/Cauchy%E2%80%93Schwarz_inequality/poMzQUIY">Cauchy–Schwarz inequality</a>.<a class="footnote-ref" id="fnref:31" href="#fn:31">31</a>
Another interpretation of these results is that the average edge length for any set of points in a unit square is 
 
 
 
 O
 (
 1
 
 /
 
 
 
 n
 
 
 )
 
 
 {\displaystyle O(1/{\sqrt {n}})}
 
, at most proportional to the spacing of points in a regular grid; and that for random points in a unit square the average length is proportional to 
 
 
 
 1
 
 /
 
 
 
 n
 
 
 
 
 {\displaystyle 1/{\sqrt {n}}}
 
. However, in the random case, with high probability the longest edge has length approximately 
 
 
 
 
 
 
 
 log
 ⁡
 n
 
 
 π
 n
 
 
 
 
 ,
 
 
 {\displaystyle {\sqrt {\frac {\log n}{\pi n}}},}
 
 longer than the average by a non-constant factor. With high probability, the longest edge forms a leaf of the spanning tree, and connects a point far from all the other points to its nearest neighbor. For large numbers of points, the distribution of the longest edge length around its expected value converges to a <a href="/facts/Gumbel_distribution/PGkDYzwe">Gumbel distribution</a>.<a class="footnote-ref" id="fnref:32" href="#fn:32">32</a>
Any <a href="/facts/Geometric_spanner/yblwj8bF">geometric spanner</a>, a subgraph of a complete geometric graph whose <a href="/facts/Shortest_path_problem/g4nsrswr">shortest paths</a> approximate the Euclidean distance, must have total edge length at least as large as the minimum spanning tree, and one of the standard quality measures for a geometric spanner is the ratio between its total length and of the minimum spanning tree for the same points. Several methods for constructing spanners, such as the <a href="/facts/Greedy_geometric_spanner/1Uqtt4aK">greedy geometric spanner</a>, achieve a constant bound for this ratio.<a class="footnote-ref" id="fnref:33" href="#fn:33">33</a> It has been conjectured that the <a href="/facts/Steiner_ratio/5mhCq8cN">Steiner ratio</a>, the largest possible ratio between the total length of a minimum spanning tree and Steiner tree for the same set of points in the plane, is 
 
 
 
 2
 
 /
 
 
 
 3
 
 
 ≈
 1.1547
 
 
 {\displaystyle 2/{\sqrt {3}}\approx 1.1547}
 
, the ratio for three points in an <a href="/facts/Equilateral_triangle/MJomsYDS">equilateral triangle</a>.<a class="footnote-ref" id="fnref:34" href="#fn:34">34</a>

<h3>Subdivision</h3>
If every edge of a Euclidean minimum spanning tree is subdivided, by adding a new point at its midpoint, then the resulting tree is still a minimum spanning tree of the augmented point set. Repeating this subdivision process allows a Euclidean minimum spanning tree to be subdivided arbitrarily finely. However, subdividing only some of the edges, or subdividing the edges at points other than the midpoint, may produce a point set for which the subdivided tree is not the minimum spanning tree.<a class="footnote-ref" id="fnref:35" href="#fn:35">35</a>

<h2 id="computational-complexity">Computational complexity</h2>
For points in any dimension, the minimum spanning tree can be constructed in time 
 
 
 
 O
 (
 
 n
 
 2
 
 
 )
 
 
 {\displaystyle O(n^{2})}
 
 by constructing a <a href="/facts/Complete_graph/AYD6hUqI">complete graph</a> with an edge between every pair of points, weighted by <a href="/facts/Euclidean_distance/9qDoQKQe">Euclidean distance</a>, and then applying a graph minimum spanning tree algorithm such as the <a href="/facts/Prim%27s_algorithm/UHEcY2lH">Prim–Dijkstra–Jarník algorithm</a> or <a href="/facts/Bor%C5%AFvka%27s_algorithm/Hs1pkNRB">Borůvka's algorithm</a> on it. These algorithms can be made to take time 
 
 
 
 O
 (
 
 n
 
 2
 
 
 )
 
 
 {\displaystyle O(n^{2})}
 
 on complete graphs, unlike another common choice, <a href="/facts/Kruskal%27s_algorithm/sg8v1BHB">Kruskal's algorithm</a>, which is slower because it involves sorting all distances.<a class="footnote-ref" id="fnref:36" href="#fn:36">36</a> For points in low-dimensional spaces, the problem may be solved more quickly, as detailed below.
Computing Euclidean distances involves a <a href="/facts/Square_root/AfrzfBdQ">square root</a> calculation. In any comparison of edge weights, comparing the squares of the Euclidean distances, instead of the distances themselves, yields the same ordering, and so does not change the rest of the tree's computation. This shortcut speeds up calculation and allows a minimum spanning tree for points with integer coordinates to be constructed using only integer arithmetic.<a class="footnote-ref" id="fnref:37" href="#fn:37">37</a>

<h3>Two dimensions</h3>
A faster approach to finding the minimum spanning tree of planar points uses the property that it is a subgraph of the Delaunay triangulation:

<ol><li>Compute the Delaunay triangulation, which can be done in 
 
 
 
 O
 (
 n
 log
 ⁡
 n
 )
 
 
 {\displaystyle O(n\log n)}
 
 time. Because the Delaunay triangulation is a <a href="/facts/Planar_graph/plREagr9">planar graph</a>, it has at most 
 
 
 
 3
 n
 −
 6
 
 
 {\displaystyle 3n-6}
 
 edges.</li>
<li>Label each edge with its (squared) length.</li>
<li>Run a graph minimum spanning tree algorithm. Since there are 
 
 
 
 O
 (
 n
 )
 
 
 {\displaystyle O(n)}
 
 edges, this requires 
 
 
 
 O
 (
 n
 log
 ⁡
 n
 )
 
 
 {\displaystyle O(n\log n)}
 
 time using any of the standard minimum spanning tree algorithms.</li></ol>
The result is an algorithm taking 
 
 
 
 O
 (
 n
 log
 ⁡
 n
 )
 
 
 {\displaystyle O(n\log n)}
 
 time,<a class="footnote-ref" id="fnref:38" href="#fn:38">38</a> optimal in certain models of computation (see below).
If the input coordinates are integers and can be used as <a href="/facts/Array_index/BKGvF8AM">array indices</a>, faster algorithms are possible: the Delaunay triangulation can be constructed by a <a href="/facts/Randomized_algorithm/Fngl1zgk">randomized algorithm</a> in 
 
 
 
 O
 (
 n
 log
 ⁡
 log
 ⁡
 n
 )
 
 
 {\displaystyle O(n\log \log n)}
 
 expected time.<a class="footnote-ref" id="fnref:39" href="#fn:39">39</a> Additionally, since the Delaunay triangulation is a <a href="/facts/Planar_graph/plREagr9">planar graph</a>, its minimum spanning tree can be found in <a href="/facts/Linear_time/77T62gmf">linear time</a> by a variant of Borůvka's algorithm that removes all but the cheapest edge between each pair of components after each stage of the algorithm.<a class="footnote-ref" id="fnref:40" href="#fn:40">40</a><a class="footnote-ref" id="fnref:41" href="#fn:41">41</a> Therefore, the total expected time for this algorithm is 
 
 
 
 O
 (
 n
 log
 ⁡
 log
 ⁡
 n
 )
 
 
 {\displaystyle O(n\log \log n)}
 
.<a class="footnote-ref" id="fnref:42" href="#fn:42">42</a> In the other direction, the Delaunay triangulation can be constructed from the minimum spanning tree in the near-linear time bound 
 
 
 
 O
 (
 n
 
 log
 
 ∗
 
 
 ⁡
 n
 )
 
 
 {\displaystyle O(n\log ^{*}n)}
 
, where 
 
 
 
 
 log
 
 ∗
 
 
 
 
 {\displaystyle \log ^{*}}
 
 denotes the <a href="/facts/Iterated_logarithm/bEY9cfh8">iterated logarithm</a>.<a class="footnote-ref" id="fnref:43" href="#fn:43">43</a>

<h3>Higher dimensions</h3>
The problem can also be generalized to 
 
 
 
 n
 
 
 {\displaystyle n}
 
 points in the 
 
 
 
 d
 
 
 {\displaystyle d}
 
-dimensional space 
 
 
 
 
 
 R
 
 
 d
 
 
 
 
 {\displaystyle \mathbb {R} ^{d}}
 
. In higher dimensions, the connectivity determined by the Delaunay triangulation (which, likewise, partitions the <a href="/facts/Convex_hull/D4Id3JDS">convex hull</a> into 
 
 
 
 d
 
 
 {\displaystyle d}
 
-dimensional <a href="/facts/Simplex/0FCfNRN8">simplices</a>) contains the minimum spanning tree; however, the triangulation might contain the complete graph.<a class="footnote-ref" id="fnref:44" href="#fn:44">44</a> Therefore, finding the Euclidean minimum spanning tree as a spanning tree of the complete graph or as a spanning tree of the Delaunay triangulation both take 
 
 
 
 O
 (
 d
 
 n
 
 2
 
 
 )
 
 
 {\displaystyle O(dn^{2})}
 
 time. For three dimensions the minimum spanning tree can be found in time 
 
 
 
 O
 
 
 (
 
 
 (
 n
 log
 ⁡
 n
 
 )
 
 4
 
 /
 
 3
 
 
 
 
 )
 
 
 
 
 {\displaystyle O{\bigl (}(n\log n)^{4/3}{\bigr )}}
 
, and in any greater dimension, in time

O
        
          (
          
            n
            
              2
              −
              
                
                  2
                  
                    ⌈
                    d
                    
                      /
                    
                    2
                    ⌉
                    +
                    1
                  
                
              
              +
              ε
            
          
          )
        
      
    
    {\displaystyle O\left(n^{2-{\frac {2}{\lceil d/2\rceil +1}}+\varepsilon }\right)}

for any 
 
 
 
 ε
 >
 0
 
 
 {\displaystyle \varepsilon >0}
 
—faster than the quadratic time bound for the complete graph and Delaunay triangulation algorithms.<a class="footnote-ref" id="fnref:45" href="#fn:45">45</a>
The optimal time complexity for higher-dimensional minimum spanning trees remains unknown,<a class="footnote-ref" id="fnref:46" href="#fn:46">46</a> but is closely related to the complexity of computing bichromatic closest pairs. In the bichromatic closest pair problem, the input is a set of points, given two different colors (say, red and blue). The output is a pair of a red point and a blue point with the minimum possible distance. This pair always forms one of the edges in the minimum spanning tree. Therefore, the bichromatic closest pair problem can be solved in the amount of time that it takes to construct a minimum spanning tree and scan its edges for the shortest red–blue edge. Conversely, for any red–blue coloring of any subset of a given set of points, the bichromatic closest pair produces one edge of the minimum spanning tree of the subset. By carefully choosing a sequence of colorings of subsets, and finding the bichromatic closest pair of each subproblem, the minimum spanning tree may be found in time proportional to the optimal time for finding bichromatic closest pairs for the same number of points, whatever that optimal time turns out to be.<a class="footnote-ref" id="fnref:47" href="#fn:47">47</a><a class="footnote-ref" id="fnref:48" href="#fn:48">48</a>
For uniformly random point sets in any bounded dimension, the <a href="/facts/Yao_graph/pdu3o4Dk">Yao graph</a><a class="footnote-ref" id="fnref:49" href="#fn:49">49</a> or Delaunay triangulation have linear expected numbers of edges, are guaranteed to contain the minimum spanning tree, and can be constructed in linear expected time.<a class="footnote-ref" id="fnref:50" href="#fn:50">50</a><a class="footnote-ref" id="fnref:51" href="#fn:51">51</a><a class="footnote-ref" id="fnref:52" href="#fn:52">52</a> From these graphs, the minimum spanning tree itself may be constructed in linear time, by using a <a href="/facts/Expected_linear_time_MST_algorithm/T0z4DrYS">randomized linear time algorithm for graph minimum spanning trees</a>.<a class="footnote-ref" id="fnref:53" href="#fn:53">53</a> However, the poor performance of these methods on inputs coming from clustered data has led <a href="/facts/Algorithm_engineering/UqPGNHzr">algorithm engineering</a> researchers to develop methods with a somewhat slower 
 
 
 
 O
 (
 n
 log
 ⁡
 n
 )
 
 
 {\displaystyle O(n\log n)}
 
 time bound, for random inputs or inputs whose distances and clustering resemble those of random data, while exhibiting better performance on real-world data.<a class="footnote-ref" id="fnref:54" href="#fn:54">54</a><a class="footnote-ref" id="fnref:55" href="#fn:55">55</a><a class="footnote-ref" id="fnref:56" href="#fn:56">56</a>
A <a href="/facts/Well-separated_pair_decomposition/lxJXArm9">well-separated pair decomposition</a> is a family of pairs of subsets of the given points, so that every pair of points belong to one of these pairs of subsets, and so that all pairs of points coming from the same pair of subsets have approximately the same length. It is possible to find a well-separated pair decomposition with a linear number of subsets, and a representative pair of points for each subset, in time 
 
 
 
 O
 (
 n
 log
 ⁡
 n
 )
 
 
 {\displaystyle O(n\log n)}
 
. The minimum spanning tree of the graph formed by these representative pairs is then an approximation to the minimum spanning tree. Using these ideas, a 
 
 
 
 (
 1
 +
 ε
 )
 
 
 {\displaystyle (1+\varepsilon )}
 
-approximation to the minimum spanning tree may be found in 
 
 
 
 O
 (
 n
 log
 ⁡
 n
 )
 
 
 {\displaystyle O(n\log n)}
 
 time, for constant 
 
 
 
 ε
 
 
 {\displaystyle \varepsilon }
 
. More precisely, by choosing each representative pair to approximate the closest pair in its equivalence class, and carefully varying the quality of this approximation for different pairs, the dependence on 
 
 
 
 ε
 
 
 {\displaystyle \varepsilon }
 
 in the time bound can be given as 
 
 
 
 O
 (
 n
 log
 ⁡
 n
 +
 (
 
 ε
 
 −
 2
 
 
 
 log
 
 2
 
 
 ⁡
 
 
 
 1
 ε
 
 
 
 )
 n
 )
 ,
 
 
 {\displaystyle O(n\log n+(\varepsilon ^{-2}\log ^{2}{\tfrac {1}{\varepsilon }})n),}
 
 for any fixed dimension.<a class="footnote-ref" id="fnref:57" href="#fn:57">57</a>

<h3>Dynamic and kinetic</h3>
The Euclidean minimum spanning tree has been generalized in many different ways to systems of moving or changing points:

<ul><li>If a set of points undergoes a sequence of dynamic insertions or deletions of points, each of these updates induces a bounded amount of change to the minimum spanning tree of the points. When the update sequence is known in advance, for points in the plane, the change after each insertion or deletion can be found in time 
 
 
 
 O
 (
 
 log
 
 2
 
 
 ⁡
 n
 )
 
 
 {\displaystyle O(\log ^{2}n)}
 
 per insertion or deletion.<a class="footnote-ref" id="fnref:58" href="#fn:58">58</a> When the updates must be handled in an <a href="/facts/Online_algorithm/64TsU7Yz">online</a> manner, a slower (but still poly-logarithmic) 
 
 
 
 O
 (
 
 log
 
 10
 
 
 ⁡
 n
 )
 
 
 {\displaystyle O(\log ^{10}n)}
 
 time bound is known.<a class="footnote-ref" id="fnref:59" href="#fn:59">59</a> For higher-dimensional versions of the problem the time per update is slower, but still sublinear.<a class="footnote-ref" id="fnref:60" href="#fn:60">60</a></li>
<li>For 
 
 
 
 n
 
 
 {\displaystyle n}
 
 points moving linearly with constant speed, or with more general algebraic motions, the minimum spanning tree will change by a sequence of swaps, in which one edge is removed and another replaces it at a point in time where both have equal length.<a class="footnote-ref" id="fnref:61" href="#fn:61">61</a> For linear motions, the number of changes is at most slightly larger than 
 
 
 
 
 n
 
 25
 
 /
 
 9
 
 
 
 
 {\displaystyle n^{25/9}}
 
.<a class="footnote-ref" id="fnref:62" href="#fn:62">62</a> For more general algebraic motions, there is a near-cubic upper bound on the number of swaps, based on the theory of <a href="/facts/Davenport%E2%80%93Schinzel_sequence/wsCPUu5B">Davenport–Schinzel sequences</a>.<a class="footnote-ref" id="fnref:63" href="#fn:63">63</a></li>
<li>The minimum moving spanning tree problem again concerns points moving linearly with constant speed, over an interval of time, and seeks a single tree that minimizes the maximum sum of weights occurring at any instant during this interval. It is <a href="/facts/NP-hard/mQeNPv4R">NP-hard</a> to compute exactly, but can be approximated to within a factor of two in polynomial time.<a class="footnote-ref" id="fnref:64" href="#fn:64">64</a></li>
<li>The <a href="/facts/Kinetic_Euclidean_minimum_spanning_tree/8hPxX9Jx">kinetic Euclidean minimum spanning tree</a> problem asks for a <a href="/facts/Kinetic_data_structure/410CqBg7">kinetic data structure</a> that can maintain the minimum spanning tree as its points undergo both continuous motions and insertions and deletions. Several papers have studied such structures,<a class="footnote-ref" id="fnref:65" href="#fn:65">65</a><a class="footnote-ref" id="fnref:66" href="#fn:66">66</a><a class="footnote-ref" id="fnref:67" href="#fn:67">67</a><a class="footnote-ref" id="fnref:68" href="#fn:68">68</a><a class="footnote-ref" id="fnref:69" href="#fn:69">69</a> and a kinetic structure for algebraically moving points with near-cubic total time, nearly matching the bound on the number of swaps, is known.<a class="footnote-ref" id="fnref:70" href="#fn:70">70</a></li></ul>
<h3>Lower bound</h3>
An asymptotic lower bound of 
 
 
 
 Ω
 (
 n
 log
 ⁡
 n
 )
 
 
 {\displaystyle \Omega (n\log n)}
 
 of the Euclidean minimum spanning tree problem can be established in restricted models of computation. These include the <a href="/facts/Algebraic_decision_tree/FalJqMSd">algebraic decision tree</a> and algebraic computation tree models, in which the algorithm has access to the input points only through certain restricted primitives that perform simple algebraic computations on their coordinates. In these models, the <a href="/facts/Closest_pair_of_points_problem/54Aw1kRV">closest pair of points problem</a> requires 
 
 
 
 Ω
 (
 n
 log
 ⁡
 n
 )
 
 
 {\displaystyle \Omega (n\log n)}
 
 time, but the closest pair is necessarily an edge of the minimum spanning tree, so the minimum spanning tree also requires this much time. Therefore, algorithms for constructing the planar minimum spanning tree in time 
 
 
 
 O
 (
 n
 log
 ⁡
 n
 )
 
 
 {\displaystyle O(n\log n)}
 
 within this model, for instance by using the Delaunay triangulation, are optimal.<a class="footnote-ref" id="fnref:71" href="#fn:71">71</a> However, these lower bounds do not apply to models of computation with integer point coordinates, in which <a href="/facts/Bitwise_operation/0gkqnUda">bitwise operations</a> and <a href="/facts/Random_access/1cxrCk3r">table indexing</a> operations on those coordinates are permitted. In these models, faster algorithms are possible, as described above.<a class="footnote-ref" id="fnref:72" href="#fn:72">72</a>

<h2 id="applications">Applications</h2>
An obvious application of Euclidean minimum spanning trees is to find the cheapest network of wires or pipes to connect a set of places, assuming the links cost a fixed amount per unit length. The first publications on minimum spanning trees more generally concerned a geographic version of the problem, involving the design of an <a href="/facts/Electrical_grid/RkWPqjmG">electrical grid</a> for <a href="/facts/South_Moravian_Region/sQKokmHn">southern Moravia</a>,<a class="footnote-ref" id="fnref:73" href="#fn:73">73</a> and an application to minimizing wire lengths in circuits was described in 1957 by Loberman and Weinberger.<a class="footnote-ref" id="fnref:74" href="#fn:74">74</a>
Minimum spanning trees are closely related to <a href="/facts/Single-linkage_clustering/suwgF2yb">single-linkage clustering</a>, one of several methods for <a href="/facts/Hierarchical_clustering/KxXs6GPK">hierarchical clustering</a>. The edges of a minimum spanning tree, sorted by their length, give the order in which to merge clusters into larger clusters in this clustering method. Once these edges have been found, by any algorithm, they may be used to construct the single-linkage clustering in time 
 
 
 
 O
 (
 n
 log
 ⁡
 n
 )
 
 
 {\displaystyle O(n\log n)}
 
.<a class="footnote-ref" id="fnref:75" href="#fn:75">75</a> Although the long thin cluster shapes produced by single-linkage clustering can be a bad fit for certain types of data, such as <a href="/facts/Mixture_model/WWe6TJlg">mixtures of Gaussian distributions</a>, it can be a good choice in applications where the clusters themselves are expected to have long thin shapes, such as in modeling the <a href="/facts/Dark_matter_halo/I6JEbRDm">dark matter halos</a> of <a href="/facts/Galaxy/zCyUvEf7">galaxies</a>.<a class="footnote-ref" id="fnref:76" href="#fn:76">76</a> In <a href="/facts/Geographic_information_science/tcKLAvuw">geographic information science</a>, several researcher groups have used minimum spanning trees of the centroids of buildings to identify meaningful clusters of buildings, for instance by removing edges identified in some other way as inconsistent.<a class="footnote-ref" id="fnref:77" href="#fn:77">77</a>
Minimum spanning trees have also been used to infer the shape of curves in the plane, given points sampled along the curve. For a smooth curve, sampled more finely than its <a href="/facts/Local_feature_size/T4pH2QJT">local feature size</a>, the minimum spanning tree will form a path connecting consecutive points along the curve. More generally, similar methods can recognize curves drawn in a dotted or dashed style rather than as a single connected set. Applications of this curve-finding technique include <a href="/facts/Particle_physics/YgIuyj2t">particle physics</a>, in automatically identifying the tracks left by particles in a <a href="/facts/Bubble_chamber/awVVhk4G">bubble chamber</a>.<a class="footnote-ref" id="fnref:78" href="#fn:78">78</a> More sophisticated versions of this idea can find curves from a cloud of noisy sample points that roughly follows the curve outline, by using the topology of the spanning tree to guide a <a href="/facts/Moving_least_squares/hwcae71G">moving least squares</a> method.<a class="footnote-ref" id="fnref:79" href="#fn:79">79</a>
Another application of minimum spanning trees is a <a href="/facts/Constant-factor_approximation_algorithm/ggqAJ3A3">constant-factor approximation algorithm</a> for the <a href="/facts/Euclidean_traveling_salesman_problem/2WEKVLnV">Euclidean traveling salesman problem</a>, the problem of finding the shortest <a href="/facts/Polygonalization/4YArjFyH">polygonalization</a> of a point set. Walking around the boundary of the minimum spanning tree can approximate the optimal traveling salesman tour within a factor of two of the optimal length.<a class="footnote-ref" id="fnref:80" href="#fn:80">80</a> However, more accurate <a href="/facts/Polynomial_time_approximation_scheme/52Chjx9y">polynomial-time approximation schemes</a> are known for this problem.<a class="footnote-ref" id="fnref:81" href="#fn:81">81</a> In <a href="/facts/Wireless_ad_hoc_network/Gwb3FlAD">wireless ad hoc networks</a>, <a href="/facts/Broadcasting_(networking)/NRj7gHre">broadcasting</a> messages along paths in a minimum spanning tree can be an accurate approximation to the minimum-energy broadcast routing, which is, again, hard to compute exactly.<a class="footnote-ref" id="fnref:82" href="#fn:82">82</a><a class="footnote-ref" id="fnref:83" href="#fn:83">83</a><a class="footnote-ref" id="fnref:84" href="#fn:84">84</a><a class="footnote-ref" id="fnref:85" href="#fn:85">85</a>

<h2 id="realization">Realization</h2>
The realization problem for Euclidean minimum spanning trees takes an abstract <a href="/facts/Tree_(graph_theory)/TCWk4Joy">tree</a> as input and seeks a geometric location for each vertex of the tree (in a space of some fixed dimension), such that the given tree equals the minimum spanning tree of those points. Not every abstract tree has such a realization; for instance, the tree must obey the <a href="/facts/Kissing_number/UE3mtV0d">kissing number</a> bound on the degree of each vertex. Additional restrictions exist; for instance, it is not possible for a planar minimum spanning tree to have a degree-six vertex adjacent to a vertex of degree five or six.<a class="footnote-ref" id="fnref:86" href="#fn:86">86</a> Determining whether a two-dimensional realization exists is <a href="/facts/NP-hard/mQeNPv4R">NP-hard</a>. However, the proof of hardness depends on the fact that degree-six vertices in a tree have a very restricted set of realizations: the neighbors of such a vertex must be placed on the vertices of a <a href="/facts/Regular_hexagon/DPzuCzWE">regular hexagon</a> centered at that vertex.<a class="footnote-ref" id="fnref:87" href="#fn:87">87</a> Indeed, for trees of maximum degree five, a planar realization always exists.<a class="footnote-ref" id="fnref:88" href="#fn:88">88</a> Similarly, for trees of maximum degree ten, a three-dimensional realization always exists.<a class="footnote-ref" id="fnref:89" href="#fn:89">89</a> For these realizations, some trees may require edges of exponential length and bounding boxes of exponential area relative to the length of their shortest edge.<a class="footnote-ref" id="fnref:90" href="#fn:90">90</a> Trees of maximum degree four have smaller planar realizations, with polynomially bounded edge lengths and bounding boxes.<a class="footnote-ref" id="fnref:91" href="#fn:91">91</a>

<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Rectilinear_minimum_spanning_tree/PB9x4R5I">Rectilinear minimum spanning tree</a>, a minimum spanning tree with distances measured using <a href="/facts/Taxicab_geometry/zU7gGUPv">taxicab geometry</a></li></ul>

<h2 id="external-links">External links</h2>
<ul><li><a href="https://mlpack.org/doc/stable/doxygen/emst_tutorial.html">EMST tutorial</a>, <a href="/facts/Mlpack/qvVhMxLL">mlpack</a> documentation</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Gower, J. C.; Ross, G. J. S. (1969), "Minimum spanning trees and single linkage cluster analysis", Applied Statistics, 18 (1): 54–61, doi:10.2307/2346439, JSTOR 2346439, MR 0242315 <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Shamos, Michael Ian; Hoey, Dan (1975), "Closest-point problems", 16th Annual Symposium on Foundations of Computer Science, Berkeley, California, USA, October 13-15, 1975, IEEE Computer Society, pp. 151–162, doi:10.1109/SFCS.1975.8, MR 0426498, S2CID 40615455 <a href="/wiki/Michael_Ian_Shamos" target="_blank">/wiki/Michael_Ian_Shamos</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Bose, Prosenjit; Devroye, Luc; Evans, William; Kirkpatrick, David (2006), "On the spanning ratio of Gabriel graphs and β-skeletons", SIAM Journal on Discrete Mathematics, 20 (2): 412–427, doi:10.1137/S0895480197318088, MR 2257270 <a href="/wiki/Jit_Bose" target="_blank">/wiki/Jit_Bose</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Agarwal, P. K.; Edelsbrunner, H.; Schwarzkopf, O.; Welzl, E. (1991), "Euclidean minimum spanning trees and bichromatic closest pairs", Discrete & Computational Geometry, 6 (1), Springer: 407–422, doi:10.1007/BF02574698, MR 1115099 <a href="/wiki/Pankaj_K._Agarwal" target="_blank">/wiki/Pankaj_K._Agarwal</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">March, William B.; Ram, Parikshit; Gray, Alexander G. (2010), "Fast Euclidean minimum spanning tree: algorithm, analysis, and applications", in Rao, Bharat; Krishnapuram, Balaji; Tomkins, Andrew; Yang, Qiang (eds.), Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Washington, DC, USA, July 25-28, 2010, pp. 603–612, doi:10.1145/1835804.1835882, S2CID 186025 <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">Clarkson, Kenneth L. (1989), "An algorithm for geometric minimum spanning trees requiring nearly linear expected time", Algorithmica, 4 (1–4): 461–469, doi:10.1007/BF01553902, MR 1019387, S2CID 22176641 <a href="/wiki/Kenneth_L._Clarkson" target="_blank">/wiki/Kenneth_L._Clarkson</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">Monma, Clyde; Suri, Subhash (1992), "Transitions in geometric minimum spanning trees", Discrete & Computational Geometry, 8 (3): 265–293, doi:10.1007/BF02293049, MR 1174358, S2CID 30101649 <a href="/wiki/Subhash_Suri" target="_blank">/wiki/Subhash_Suri</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">Narasimhan, Giri; Zachariasen, Martin; Zhu, Jianlin (2000), "Experiments with computing geometric minimum spanning trees", Proceedings of the 2nd Workshop on Algorithm Engineering and Experiments, pp. 183–196 <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
<li id="fn:9">Frati, Fabrizio; Kaufmann, Michael (2011), "Polynomial area bounds for MST embeddings of trees", Computational Geometry: Theory and Applications, 44 (9): 529–543, doi:10.1016/j.comgeo.2011.05.005, MR 2819643, S2CID 5634139 <a href="/wiki/Computational_Geometry_(journal)" target="_blank">/wiki/Computational_Geometry_(journal)</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></li>
<li id="fn:10">King, James A. (2006), "Realization of degree 10 minimum spanning trees in 3-space" (PDF), Proceedings of the 18th Annual Canadian Conference on Computational Geometry, CCCG 2006, August 14-16, 2006, Queen's University, Ontario, Canada, pp. 39–42 <a href="https://www.cs.queensu.ca/cccg/papers/cccg11.pdf" target="_blank">https://www.cs.queensu.ca/cccg/papers/cccg11.pdf</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></li>
<li id="fn:11">Krznaric, Drago; Levcopoulos, Christos; Nilsson, Bengt J. (1999), "Minimum spanning trees in 
 
 
 
 d
 
 
 {\displaystyle d}
 
 dimensions", Nordic Journal of Computing, 6 (4): 446–461, MR 1736451. This version of this paper is not available online; instead, see the 1997 conference version of the same paper, doi:10.1007/3-540-63397-9_26. <a href="/wiki/MR_(identifier)" target="_blank">/wiki/MR_(identifier)</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></li>
<li id="fn:12">Gilbert, E. N.; Pollak, H. O. (1968), "Steiner minimal trees", SIAM Journal on Applied Mathematics, 16 (1): 1–29, doi:10.1137/0116001, JSTOR 2099400, MR 0223269 <a href="/wiki/Edgar_Gilbert" target="_blank">/wiki/Edgar_Gilbert</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></li>
<li id="fn:13">Shamos, Michael Ian; Hoey, Dan (1975), "Closest-point problems", 16th Annual Symposium on Foundations of Computer Science, Berkeley, California, USA, October 13-15, 1975, IEEE Computer Society, pp. 151–162, doi:10.1109/SFCS.1975.8, MR 0426498, S2CID 40615455 <a href="/wiki/Michael_Ian_Shamos" target="_blank">/wiki/Michael_Ian_Shamos</a> <a href="#fnref:13" class="footnote-back-ref">↩</a></li>
<li id="fn:14">Eppstein, David (1999), "Spanning trees and spanners" (PDF), in Sack, J.-R.; Urrutia, J. (eds.), Handbook of Computational Geometry, Elsevier, pp. 425–461, MR 1746681 <a href="/wiki/David_Eppstein" target="_blank">/wiki/David_Eppstein</a> <a href="#fnref:14" class="footnote-back-ref">↩</a></li>
<li id="fn:15">Georgakopoulos, George; Papadimitriou, Christos H. (1987), "The 1-Steiner tree problem", Journal of Algorithms, 8 (1): 122–130, doi:10.1016/0196-6774(87)90032-0, MR 0875330 <a href="/wiki/Christos_Papadimitriou" target="_blank">/wiki/Christos_Papadimitriou</a> <a href="#fnref:15" class="footnote-back-ref">↩</a></li>
<li id="fn:16">Gilbert, E. N.; Pollak, H. O. (1968), "Steiner minimal trees", SIAM Journal on Applied Mathematics, 16 (1): 1–29, doi:10.1137/0116001, JSTOR 2099400, MR 0223269 <a href="/wiki/Edgar_Gilbert" target="_blank">/wiki/Edgar_Gilbert</a> <a href="#fnref:16" class="footnote-back-ref">↩</a></li>
<li id="fn:17">Robins, G.; Salowe, J. S. (1995), "Low-degree minimum spanning trees", Discrete & Computational Geometry, 14 (2): 151–165, doi:10.1007/BF02570700, MR 1331924, S2CID 16040977 <a href="/wiki/Discrete_%26_Computational_Geometry" target="_blank">/wiki/Discrete_%26_Computational_Geometry</a> <a href="#fnref:17" class="footnote-back-ref">↩</a></li>
<li id="fn:18">Monma, Clyde; Suri, Subhash (1992), "Transitions in geometric minimum spanning trees", Discrete & Computational Geometry, 8 (3): 265–293, doi:10.1007/BF02293049, MR 1174358, S2CID 30101649 <a href="/wiki/Subhash_Suri" target="_blank">/wiki/Subhash_Suri</a> <a href="#fnref:18" class="footnote-back-ref">↩</a></li>
<li id="fn:19">Robins, G.; Salowe, J. S. (1995), "Low-degree minimum spanning trees", Discrete & Computational Geometry, 14 (2): 151–165, doi:10.1007/BF02570700, MR 1331924, S2CID 16040977 <a href="/wiki/Discrete_%26_Computational_Geometry" target="_blank">/wiki/Discrete_%26_Computational_Geometry</a> <a href="#fnref:19" class="footnote-back-ref">↩</a></li>
<li id="fn:20">Pfender, Florian; Ziegler, Günter M. (September 2004), "Kissing numbers, sphere packings, and some unexpected proofs" (PDF), Notices of the American Mathematical Society: 873–883 <a href="/wiki/G%C3%BCnter_M._Ziegler" target="_blank">/wiki/G%C3%BCnter_M._Ziegler</a> <a href="#fnref:20" class="footnote-back-ref">↩</a></li>
<li id="fn:21">Steele, J. Michael; Shepp, Lawrence A.; Eddy, William F. (1987), "On the number of leaves of a Euclidean minimal spanning tree", Journal of Applied Probability, 24 (4): 809–826, doi:10.2307/3214207, JSTOR 3214207, MR 0913823, S2CID 29026025 <a href="/wiki/J._Michael_Steele" target="_blank">/wiki/J._Michael_Steele</a> <a href="#fnref:21" class="footnote-back-ref">↩</a></li>
<li id="fn:22">Gilbert, E. N.; Pollak, H. O. (1968), "Steiner minimal trees", SIAM Journal on Applied Mathematics, 16 (1): 1–29, doi:10.1137/0116001, JSTOR 2099400, MR 0223269 <a href="/wiki/Edgar_Gilbert" target="_blank">/wiki/Edgar_Gilbert</a> <a href="#fnref:22" class="footnote-back-ref">↩</a></li>
<li id="fn:23">Gilbert, E. N.; Pollak, H. O. (1968), "Steiner minimal trees", SIAM Journal on Applied Mathematics, 16 (1): 1–29, doi:10.1137/0116001, JSTOR 2099400, MR 0223269 <a href="/wiki/Edgar_Gilbert" target="_blank">/wiki/Edgar_Gilbert</a> <a href="#fnref:23" class="footnote-back-ref">↩</a></li>
<li id="fn:24">Preparata, Franco P.; Shamos, Michael Ian (1985), Computational Geometry: An Introduction, Texts and Monographs in Computer Science, Springer-Verlag, New York, p. 263, doi:10.1007/978-1-4612-1098-6, ISBN 0-387-96131-3, MR 0805539, S2CID 206656565 <a href="0-387-96131-3" target="_blank">0-387-96131-3</a> <a href="#fnref:24" class="footnote-back-ref">↩</a></li>
<li id="fn:25">Toussaint, G. T. (1980), "Comment: Algorithms for computing relative neighborhood graph", Electronics Letters, 16 (22): 860, Bibcode:1980ElL....16..860T, doi:10.1049/el:19800611; reply by Urquhart, pp. 860–861 <a href="/wiki/Godfried_Toussaint" target="_blank">/wiki/Godfried_Toussaint</a> <a href="#fnref:25" class="footnote-back-ref">↩</a></li>
<li id="fn:26">Yao, Andrew Chi Chih (1982), "On constructing minimum spanning trees in k-dimensional spaces and related problems", SIAM Journal on Computing, 11 (4): 721–736, doi:10.1137/0211059, MR 0677663 <a href="/wiki/Andrew_Yao" target="_blank">/wiki/Andrew_Yao</a> <a href="#fnref:26" class="footnote-back-ref">↩</a></li>
<li id="fn:27">Bentley, Jon Louis; Weide, Bruce W.; Yao, Andrew C. (1980), "Optimal expected-time algorithms for closest point problems", ACM Transactions on Mathematical Software, 6 (4): 563–580, doi:10.1145/355921.355927, MR 0599977, S2CID 17238717 <a href="/wiki/Jon_Bentley_(computer_scientist)" target="_blank">/wiki/Jon_Bentley_(computer_scientist)</a> <a href="#fnref:27" class="footnote-back-ref">↩</a></li>
<li id="fn:28">Gilbert, E. N.; Pollak, H. O. (1968), "Steiner minimal trees", SIAM Journal on Applied Mathematics, 16 (1): 1–29, doi:10.1137/0116001, JSTOR 2099400, MR 0223269 <a href="/wiki/Edgar_Gilbert" target="_blank">/wiki/Edgar_Gilbert</a> <a href="#fnref:28" class="footnote-back-ref">↩</a></li>
<li id="fn:29">Steele, J. Michael; Snyder, Timothy Law (1989), "Worst-case growth rates of some classical problems of combinatorial optimization", SIAM Journal on Computing, 18 (2): 278–287, doi:10.1137/0218019, MR 0986667 <a href="/wiki/J._Michael_Steele" target="_blank">/wiki/J._Michael_Steele</a> <a href="#fnref:29" class="footnote-back-ref">↩</a></li>
<li id="fn:30">Steele, J. Michael (1988), "Growth rates of Euclidean minimal spanning trees with power weighted edges", Annals of Probability, 16 (4): 1767–1787, doi:10.1214/aop/1176991596, JSTOR 2243991, MR 0958215 <a href="/wiki/J._Michael_Steele" target="_blank">/wiki/J._Michael_Steele</a> <a href="#fnref:30" class="footnote-back-ref">↩</a></li>
<li id="fn:31">Gilbert, E. N.; Pollak, H. O. (1968), "Steiner minimal trees", SIAM Journal on Applied Mathematics, 16 (1): 1–29, doi:10.1137/0116001, JSTOR 2099400, MR 0223269 <a href="/wiki/Edgar_Gilbert" target="_blank">/wiki/Edgar_Gilbert</a> <a href="#fnref:31" class="footnote-back-ref">↩</a></li>
<li id="fn:32">Penrose, Mathew D. (1997), "The longest edge of the random minimal spanning tree", The Annals of Applied Probability, 7 (2): 340–361, doi:10.1214/aoap/1034625335, MR 1442317 <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:32" class="footnote-back-ref">↩</a></li>
<li id="fn:33">Eppstein, David (1999), "Spanning trees and spanners" (PDF), in Sack, J.-R.; Urrutia, J. (eds.), Handbook of Computational Geometry, Elsevier, pp. 425–461, MR 1746681 <a href="/wiki/David_Eppstein" target="_blank">/wiki/David_Eppstein</a> <a href="#fnref:33" class="footnote-back-ref">↩</a></li>
<li id="fn:34">Gilbert, E. N.; Pollak, H. O. (1968), "Steiner minimal trees", SIAM Journal on Applied Mathematics, 16 (1): 1–29, doi:10.1137/0116001, JSTOR 2099400, MR 0223269 <a href="/wiki/Edgar_Gilbert" target="_blank">/wiki/Edgar_Gilbert</a> <a href="#fnref:34" class="footnote-back-ref">↩</a></li>
<li id="fn:35">Boyce, W. M.; Garey, M. R.; Johnson, D. S. (1978), "A note on bisecting minimum spanning trees", Networks, 8 (3): 187–192, doi:10.1002/net.3230080302, MR 0491324 <a href="/wiki/Michael_Garey" target="_blank">/wiki/Michael_Garey</a> <a href="#fnref:35" class="footnote-back-ref">↩</a></li>
<li id="fn:36">Eppstein, David (1999), "Spanning trees and spanners" (PDF), in Sack, J.-R.; Urrutia, J. (eds.), Handbook of Computational Geometry, Elsevier, pp. 425–461, MR 1746681 <a href="/wiki/David_Eppstein" target="_blank">/wiki/David_Eppstein</a> <a href="#fnref:36" class="footnote-back-ref">↩</a></li>
<li id="fn:37">Yao, Andrew Chi Chih (1982), "On constructing minimum spanning trees in k-dimensional spaces and related problems", SIAM Journal on Computing, 11 (4): 721–736, doi:10.1137/0211059, MR 0677663 <a href="/wiki/Andrew_Yao" target="_blank">/wiki/Andrew_Yao</a> <a href="#fnref:37" class="footnote-back-ref">↩</a></li>
<li id="fn:38">Shamos, Michael Ian; Hoey, Dan (1975), "Closest-point problems", 16th Annual Symposium on Foundations of Computer Science, Berkeley, California, USA, October 13-15, 1975, IEEE Computer Society, pp. 151–162, doi:10.1109/SFCS.1975.8, MR 0426498, S2CID 40615455 <a href="/wiki/Michael_Ian_Shamos" target="_blank">/wiki/Michael_Ian_Shamos</a> <a href="#fnref:38" class="footnote-back-ref">↩</a></li>
<li id="fn:39">Buchin, Kevin; Mulzer, Wolfgang (2011), "Delaunay triangulations in O(sort(n)) time and more", Journal of the ACM, 58 (2): A6:1–A6:27, doi:10.1145/1944345.1944347, MR 2786587, S2CID 11316974 <a href="/wiki/Journal_of_the_ACM" target="_blank">/wiki/Journal_of_the_ACM</a> <a href="#fnref:39" class="footnote-back-ref">↩</a></li>
<li id="fn:40">Eppstein, David (1999), "Spanning trees and spanners" (PDF), in Sack, J.-R.; Urrutia, J. (eds.), Handbook of Computational Geometry, Elsevier, pp. 425–461, MR 1746681 <a href="/wiki/David_Eppstein" target="_blank">/wiki/David_Eppstein</a> <a href="#fnref:40" class="footnote-back-ref">↩</a></li>
<li id="fn:41">Mareš, Martin (2004), "Two linear time algorithms for MST on minor closed graph classes" (PDF), Archivum Mathematicum, 40 (3): 315–320, MR 2107027 <a href="https://www.emis.de/journals/AM/04-3/am1139.pdf" target="_blank">https://www.emis.de/journals/AM/04-3/am1139.pdf</a> <a href="#fnref:41" class="footnote-back-ref">↩</a></li>
<li id="fn:42">Buchin, Kevin; Mulzer, Wolfgang (2011), "Delaunay triangulations in O(sort(n)) time and more", Journal of the ACM, 58 (2): A6:1–A6:27, doi:10.1145/1944345.1944347, MR 2786587, S2CID 11316974 <a href="/wiki/Journal_of_the_ACM" target="_blank">/wiki/Journal_of_the_ACM</a> <a href="#fnref:42" class="footnote-back-ref">↩</a></li>
<li id="fn:43">Devillers, Olivier (1992), "Randomization yields simple O(n log* n) algorithms for difficult Ω(n) problems" (PDF), International Journal of Computational Geometry & Applications, 2 (1): 97–111, doi:10.1142/S021819599200007X, MR 1159844, S2CID 60203 <a href="https://hal.inria.fr/inria-00167206/file/hal.pdf" target="_blank">https://hal.inria.fr/inria-00167206/file/hal.pdf</a> <a href="#fnref:43" class="footnote-back-ref">↩</a></li>
<li id="fn:44">Agarwal, P. K.; Edelsbrunner, H.; Schwarzkopf, O.; Welzl, E. (1991), "Euclidean minimum spanning trees and bichromatic closest pairs", Discrete & Computational Geometry, 6 (1), Springer: 407–422, doi:10.1007/BF02574698, MR 1115099 <a href="/wiki/Pankaj_K._Agarwal" target="_blank">/wiki/Pankaj_K._Agarwal</a> <a href="#fnref:44" class="footnote-back-ref">↩</a></li>
<li id="fn:45">Agarwal, P. K.; Edelsbrunner, H.; Schwarzkopf, O.; Welzl, E. (1991), "Euclidean minimum spanning trees and bichromatic closest pairs", Discrete & Computational Geometry, 6 (1), Springer: 407–422, doi:10.1007/BF02574698, MR 1115099 <a href="/wiki/Pankaj_K._Agarwal" target="_blank">/wiki/Pankaj_K._Agarwal</a> <a href="#fnref:45" class="footnote-back-ref">↩</a></li>
<li id="fn:46">O'Rourke, J.; Demaine, E. (2001–2002), "Problem 5: Euclidean Minimum Spanning Tree", The Open Problems Project, Smith College <a href="/wiki/Joseph_O%27Rourke_(professor)" target="_blank">/wiki/Joseph_O%27Rourke_(professor)</a> <a href="#fnref:46" class="footnote-back-ref">↩</a></li>
<li id="fn:47">Agarwal, P. K.; Edelsbrunner, H.; Schwarzkopf, O.; Welzl, E. (1991), "Euclidean minimum spanning trees and bichromatic closest pairs", Discrete & Computational Geometry, 6 (1), Springer: 407–422, doi:10.1007/BF02574698, MR 1115099 <a href="/wiki/Pankaj_K._Agarwal" target="_blank">/wiki/Pankaj_K._Agarwal</a> <a href="#fnref:47" class="footnote-back-ref">↩</a></li>
<li id="fn:48">Krznaric, Drago; Levcopoulos, Christos; Nilsson, Bengt J. (1999), "Minimum spanning trees in 
 
 
 
 d
 
 
 {\displaystyle d}
 
 dimensions", Nordic Journal of Computing, 6 (4): 446–461, MR 1736451. This version of this paper is not available online; instead, see the 1997 conference version of the same paper, doi:10.1007/3-540-63397-9_26. <a href="/wiki/MR_(identifier)" target="_blank">/wiki/MR_(identifier)</a> <a href="#fnref:48" class="footnote-back-ref">↩</a></li>
<li id="fn:49">Yao, Andrew Chi Chih (1982), "On constructing minimum spanning trees in k-dimensional spaces and related problems", SIAM Journal on Computing, 11 (4): 721–736, doi:10.1137/0211059, MR 0677663 <a href="/wiki/Andrew_Yao" target="_blank">/wiki/Andrew_Yao</a> <a href="#fnref:49" class="footnote-back-ref">↩</a></li>
<li id="fn:50">Bentley, Jon Louis; Weide, Bruce W.; Yao, Andrew C. (1980), "Optimal expected-time algorithms for closest point problems", ACM Transactions on Mathematical Software, 6 (4): 563–580, doi:10.1145/355921.355927, MR 0599977, S2CID 17238717 <a href="/wiki/Jon_Bentley_(computer_scientist)" target="_blank">/wiki/Jon_Bentley_(computer_scientist)</a> <a href="#fnref:50" class="footnote-back-ref">↩</a></li>
<li id="fn:51">Clarkson, Kenneth L. (1989), "An algorithm for geometric minimum spanning trees requiring nearly linear expected time", Algorithmica, 4 (1–4): 461–469, doi:10.1007/BF01553902, MR 1019387, S2CID 22176641 <a href="/wiki/Kenneth_L._Clarkson" target="_blank">/wiki/Kenneth_L._Clarkson</a> <a href="#fnref:51" class="footnote-back-ref">↩</a></li>
<li id="fn:52">Dwyer, Rex A. (1991), "Higher-dimensional Voronoi diagrams in linear expected time", Discrete & Computational Geometry, 6 (4): 343–367, doi:10.1007/BF02574694, MR 1098813 <a href="/wiki/Discrete_%26_Computational_Geometry" target="_blank">/wiki/Discrete_%26_Computational_Geometry</a> <a href="#fnref:52" class="footnote-back-ref">↩</a></li>
<li id="fn:53">Karger, David R.; Klein, Philip N.; Tarjan, Robert E. (1995), "A randomized linear-time algorithm to find minimum spanning trees", Journal of the ACM, 42 (2): 321–328, doi:10.1145/201019.201022, MR 1409738, S2CID 832583 <a href="/wiki/David_Karger" target="_blank">/wiki/David_Karger</a> <a href="#fnref:53" class="footnote-back-ref">↩</a></li>
<li id="fn:54">Narasimhan, Giri; Zachariasen, Martin; Zhu, Jianlin (2000), "Experiments with computing geometric minimum spanning trees", Proceedings of the 2nd Workshop on Algorithm Engineering and Experiments, pp. 183–196 <a href="#fnref:54" class="footnote-back-ref">↩</a></li>
<li id="fn:55">Chatterjee, S.; Connor, M.; Kumar, P. (2010), "Geometric minimum spanning trees with GeoFilterKruskal", in Festa, Paola (ed.), Experimental Algorithms: 9th International Symposium, SEA 2010, Ischia Island, Naples, Italy, May 20-22, 2010, Proceedings, Lecture Notes in Computer Science, vol. 6049, Springer-Verlag, pp. 486–500, doi:10.1007/978-3-642-13193-6_41, ISBN 978-3-642-13192-9 <a href="978-3-642-13192-9" target="_blank">978-3-642-13192-9</a> <a href="#fnref:55" class="footnote-back-ref">↩</a></li>
<li id="fn:56">March, William B.; Ram, Parikshit; Gray, Alexander G. (2010), "Fast Euclidean minimum spanning tree: algorithm, analysis, and applications", in Rao, Bharat; Krishnapuram, Balaji; Tomkins, Andrew; Yang, Qiang (eds.), Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Washington, DC, USA, July 25-28, 2010, pp. 603–612, doi:10.1145/1835804.1835882, S2CID 186025 <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:56" class="footnote-back-ref">↩</a></li>
<li id="fn:57">Arya, Sunil; Mount, David M. (2016), "A fast and simple algorithm for computing approximate Euclidean minimum spanning trees", in Krauthgamer, Robert (ed.), Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pp. 1220–1233, doi:10.1137/1.9781611974331.ch85, ISBN 978-1-61197-433-1, MR 3478461 <a href="978-1-61197-433-1" target="_blank">978-1-61197-433-1</a> <a href="#fnref:57" class="footnote-back-ref">↩</a></li>
<li id="fn:58">Eppstein, David (1994), "Offline algorithms for dynamic minimum spanning tree problems", Journal of Algorithms, 17 (2): 237–250, doi:10.1006/jagm.1994.1033, MR 1291541 <a href="/wiki/David_Eppstein" target="_blank">/wiki/David_Eppstein</a> <a href="#fnref:58" class="footnote-back-ref">↩</a></li>
<li id="fn:59">Chan, Timothy M. (2010), "A dynamic data structure for 3-D convex hulls and 2-D nearest neighbor queries", Journal of the ACM, 57 (3): Article 16, doi:10.1145/1706591.1706596, MR 2665885, S2CID 47454142 <a href="/wiki/Timothy_M._Chan" target="_blank">/wiki/Timothy_M._Chan</a> <a href="#fnref:59" class="footnote-back-ref">↩</a></li>
<li id="fn:60">Eppstein, David (1995), "Dynamic Euclidean minimum spanning trees and extrema of binary functions", Discrete & Computational Geometry, 13 (1): 111–122, doi:10.1007/BF02574030, MR 1300511, S2CID 7339165 <a href="/wiki/David_Eppstein" target="_blank">/wiki/David_Eppstein</a> <a href="#fnref:60" class="footnote-back-ref">↩</a></li>
<li id="fn:61">Katoh, N.; Tokuyama, T.; Iwano, K. (1995), "On minimum and maximum spanning trees of linearly moving points", Discrete & Computational Geometry, 13 (2): 161–176, doi:10.1007/BF02574035, MR 1314960 <a href="/wiki/Discrete_%26_Computational_Geometry" target="_blank">/wiki/Discrete_%26_Computational_Geometry</a> <a href="#fnref:61" class="footnote-back-ref">↩</a></li>
<li id="fn:62">Chan, Timothy M. (2003), "On levels in arrangements of curves", Discrete & Computational Geometry, 29 (3): 375–393, doi:10.1007/s00454-002-2840-2, MR 1961005, S2CID 18966889 <a href="/wiki/Timothy_M._Chan" target="_blank">/wiki/Timothy_M._Chan</a> <a href="#fnref:62" class="footnote-back-ref">↩</a></li>
<li id="fn:63">Rahmati, Zahed; Zarei, Alireza (2010), "Combinatorial changes of Euclidean minimum spanning tree of moving points in the plane" (PDF), Proceedings of the 22nd Annual Canadian Conference on Computational Geometry, Winnipeg, Manitoba, Canada, August 9-11, 2010, pp. 43–45 <a href="https://cccg.ca/proceedings/2010/paper14.pdf" target="_blank">https://cccg.ca/proceedings/2010/paper14.pdf</a> <a href="#fnref:63" class="footnote-back-ref">↩</a></li>
<li id="fn:64">Akitaya, Hugo A.; Biniaz, Ahmad; Bose, Prosenjit; De Carufel, Jean-Lou; Maheshwari, Anil; da Silveira, Luís Fernando Schultz Xavier; Smid, Michiel (2021), "The minimum moving spanning tree problem", in Lubiw, Anna; Salavatipour, Mohammad R. (eds.), Algorithms and Data Structures: 17th International Symposium, WADS 2021, Virtual Event, August 9–11, 2021, Proceedings, Lecture Notes in Computer Science, vol. 12808, Springer, pp. 15–28, doi:10.1007/978-3-030-83508-8_2, ISBN 978-3-030-83507-1, S2CID 234599877 <a href="978-3-030-83507-1" target="_blank">978-3-030-83507-1</a> <a href="#fnref:64" class="footnote-back-ref">↩</a></li>
<li id="fn:65">Basch, Julien; Guibas, Leonidas J.; Zhang, Li (1997), "Proximity problems on moving points", in Boissonnat, Jean-Daniel (ed.), Proceedings of the Thirteenth Annual Symposium on Computational Geometry, Nice, France, June 4–6, 1997, Association for Computing Machinery, pp. 344–351, doi:10.1145/262839.262998, ISBN 0-89791-878-9, S2CID 15556637 <a href="0-89791-878-9" target="_blank">0-89791-878-9</a> <a href="#fnref:65" class="footnote-back-ref">↩</a></li>
<li id="fn:66">Agarwal, Pankaj K.; Eppstein, David; Guibas, Leonidas J.; Henzinger, Monika Rauch (1998), "Parametric and Kinetic Minimum Spanning Trees", 39th Annual Symposium on Foundations of Computer Science, FOCS '98, November 8–11, 1998, Palo Alto, California, USA (PDF), IEEE Computer Society, pp. 596–605, doi:10.1109/SFCS.1998.743510, ISBN 0-8186-9172-7, S2CID 2559456 <a href="0-8186-9172-7" target="_blank">0-8186-9172-7</a> <a href="#fnref:66" class="footnote-back-ref">↩</a></li>
<li id="fn:67">Rahmati, Zahed; Zarei, Alireza (2012), "Kinetic Euclidean minimum spanning tree in the plane", Journal of Discrete Algorithms, 16: 2–11, doi:10.1016/j.jda.2012.04.009, MR 2960341 <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:67" class="footnote-back-ref">↩</a></li>
<li id="fn:68">Rahmati, Zahed; Abam, Mohammad Ali; King, Valerie; Whitesides, Sue; Zarei, Alireza (2015), "A simple, faster method for kinetic proximity problems", Computational Geometry: Theory & Applications, 48 (4): 342–359, arXiv:1311.2032, doi:10.1016/j.comgeo.2014.12.002, MR 3296072, S2CID 18971251 <a href="/wiki/Valerie_King" target="_blank">/wiki/Valerie_King</a> <a href="#fnref:68" class="footnote-back-ref">↩</a></li>
<li id="fn:69">Meulemans, Wouter; Speckmann, Bettina; Verbeek, Kevin; Wulms, Jules (2018), "A framework for algorithm stability and its application to kinetic Euclidean MSTs", in Bender, Michael A.; Farach-Colton, Martin; Mosteiro, Miguel A. (eds.), LATIN 2018: Theoretical Informatics – 13th Latin American Symposium, Buenos Aires, Argentina, April 16–19, 2018, Proceedings, Lecture Notes in Computer Science, vol. 10807, Springer, pp. 805–819, doi:10.1007/978-3-319-77404-6_58, ISBN 978-3-319-77403-9, S2CID 4709616 <a href="978-3-319-77403-9" target="_blank">978-3-319-77403-9</a> <a href="#fnref:69" class="footnote-back-ref">↩</a></li>
<li id="fn:70">Rahmati, Zahed; Abam, Mohammad Ali; King, Valerie; Whitesides, Sue; Zarei, Alireza (2015), "A simple, faster method for kinetic proximity problems", Computational Geometry: Theory & Applications, 48 (4): 342–359, arXiv:1311.2032, doi:10.1016/j.comgeo.2014.12.002, MR 3296072, S2CID 18971251 <a href="/wiki/Valerie_King" target="_blank">/wiki/Valerie_King</a> <a href="#fnref:70" class="footnote-back-ref">↩</a></li>
<li id="fn:71">Yao, Andrew Chi-Chih (1991), "Lower bounds for algebraic computation trees with integer inputs", SIAM Journal on Computing, 20 (4): 655–668, doi:10.1137/0220041, MR 1105929 <a href="/wiki/Andrew_Yao" target="_blank">/wiki/Andrew_Yao</a> <a href="#fnref:71" class="footnote-back-ref">↩</a></li>
<li id="fn:72">Buchin, Kevin; Mulzer, Wolfgang (2011), "Delaunay triangulations in O(sort(n)) time and more", Journal of the ACM, 58 (2): A6:1–A6:27, doi:10.1145/1944345.1944347, MR 2786587, S2CID 11316974 <a href="/wiki/Journal_of_the_ACM" target="_blank">/wiki/Journal_of_the_ACM</a> <a href="#fnref:72" class="footnote-back-ref">↩</a></li>
<li id="fn:73">Graham, R. L.; Hell, Pavol (1985), "On the history of the minimum spanning tree problem", IEEE Annals of the History of Computing, 7 (1): 43–57, doi:10.1109/mahc.1985.10011, MR 0783327, S2CID 10555375 <a href="/wiki/Ronald_Graham" target="_blank">/wiki/Ronald_Graham</a> <a href="#fnref:73" class="footnote-back-ref">↩</a></li>
<li id="fn:74">Loberman, H.; Weinberger, A. (October 1957), "Formal procedures for connecting terminals with a minimum total wire length", Journal of the ACM, 4 (4): 428–437, doi:10.1145/320893.320896, S2CID 7320964 <a href="/wiki/Journal_of_the_ACM" target="_blank">/wiki/Journal_of_the_ACM</a> <a href="#fnref:74" class="footnote-back-ref">↩</a></li>
<li id="fn:75">Gower, J. C.; Ross, G. J. S. (1969), "Minimum spanning trees and single linkage cluster analysis", Applied Statistics, 18 (1): 54–61, doi:10.2307/2346439, JSTOR 2346439, MR 0242315 <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:75" class="footnote-back-ref">↩</a></li>
<li id="fn:76">March, William B.; Ram, Parikshit; Gray, Alexander G. (2010), "Fast Euclidean minimum spanning tree: algorithm, analysis, and applications", in Rao, Bharat; Krishnapuram, Balaji; Tomkins, Andrew; Yang, Qiang (eds.), Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Washington, DC, USA, July 25-28, 2010, pp. 603–612, doi:10.1145/1835804.1835882, S2CID 186025 <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:76" class="footnote-back-ref">↩</a></li>
<li id="fn:77">Wu, Bin; Yu, Bailang; Wu, Qiusheng; Chen, Zuoqi; Yao, Shenjun; Huang, Yan; Wu, Jianping (October 2017), "An extended minimum spanning tree method for characterizing local urban patterns", International Journal of Geographical Information Science, 32 (3): 450–475, doi:10.1080/13658816.2017.1384830, S2CID 46772272 <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:77" class="footnote-back-ref">↩</a></li>
<li id="fn:78">Zahn, C. T. (1973), "Using the minimum spanning tree to recognize dotted and dashed curves", 1st International Computing Symposium, Davos, Switzerland, 4–7 September 1973 <a href="https://cds.cern.ch/record/1050916" target="_blank">https://cds.cern.ch/record/1050916</a> <a href="#fnref:78" class="footnote-back-ref">↩</a></li>
<li id="fn:79">Lee, In-Kwon (2000), "Curve reconstruction from unorganized points", Computer Aided Geometric Design, 17 (2): 161–177, CiteSeerX 10.1.1.56.1432, doi:10.1016/S0167-8396(99)00044-8, MR 1733203 <a href="/wiki/CiteSeerX_(identifier)" target="_blank">/wiki/CiteSeerX_(identifier)</a> <a href="#fnref:79" class="footnote-back-ref">↩</a></li>
<li id="fn:80">Shamos, Michael Ian; Hoey, Dan (1975), "Closest-point problems", 16th Annual Symposium on Foundations of Computer Science, Berkeley, California, USA, October 13-15, 1975, IEEE Computer Society, pp. 151–162, doi:10.1109/SFCS.1975.8, MR 0426498, S2CID 40615455 <a href="/wiki/Michael_Ian_Shamos" target="_blank">/wiki/Michael_Ian_Shamos</a> <a href="#fnref:80" class="footnote-back-ref">↩</a></li>
<li id="fn:81">Bartal, Yair; Gottlieb, Lee-Ad (2013), "A linear time approximation scheme for Euclidean TSP", 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, 26-29 October, 2013, Berkeley, CA, USA, pp. 698–706, CiteSeerX 10.1.1.409.1291, doi:10.1109/FOCS.2013.80, ISBN 978-0-7695-5135-7, MR 3246273, S2CID 17514182 <a href="978-0-7695-5135-7" target="_blank">978-0-7695-5135-7</a> <a href="#fnref:81" class="footnote-back-ref">↩</a></li>
<li id="fn:82">Wan, P.-J.; Călinescu, G.; Li, X.-Y.; Frieder, O. (2002), "Minimum-energy broadcasting in static ad hoc wireless networks", Wireless Networks, 8 (6): 607–617, doi:10.1023/a:1020381720601, S2CID 1297518 <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:82" class="footnote-back-ref">↩</a></li>
<li id="fn:83">Clementi, Andrea E. F.; Huiban, Gurvan; Rossi, Gianluca; Verhoeven, Yann C.; Penna, Paolo (2003), "On the approximation ratio of the MST-based heuristic for the energy-efficient broadcast problem in static ad-hoc radio networks", 17th International Parallel and Distributed Processing Symposium (IPDPS 2003), 22-26 April 2003, Nice, France, Proceedings, IEEE Computer Society, p. 222, doi:10.1109/IPDPS.2003.1213407, ISBN 0-7695-1926-1, S2CID 17863487 <a href="0-7695-1926-1" target="_blank">0-7695-1926-1</a> <a href="#fnref:83" class="footnote-back-ref">↩</a></li>
<li id="fn:84">Flammini, Michele; Klasing, Ralf; Navarra, Alfredo; Perennes, Stephane (2007), "Improved approximation results for the minimum energy broadcasting problem", Algorithmica, 49 (4): 318–336, doi:10.1007/s00453-007-9077-7, MR 2358524, S2CID 11982404 <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:84" class="footnote-back-ref">↩</a></li>
<li id="fn:85">Ambühl, Christoph (2005), "An optimal bound for the MST algorithm to compute energy efficient broadcast trees in wireless networks", in Caires, Luís; Italiano, Giuseppe F.; Monteiro, Luís; Palamidessi, Catuscia; Yung, Moti (eds.), Automata, Languages and Programming, 32nd International Colloquium, ICALP 2005, Lisbon, Portugal, July 11-15, 2005, Proceedings, Lecture Notes in Computer Science, vol. 3580, Springer, pp. 1139–1150, doi:10.1007/11523468_92, ISBN 978-3-540-27580-0 <a href="978-3-540-27580-0" target="_blank">978-3-540-27580-0</a> <a href="#fnref:85" class="footnote-back-ref">↩</a></li>
<li id="fn:86">Monma, Clyde; Suri, Subhash (1992), "Transitions in geometric minimum spanning trees", Discrete & Computational Geometry, 8 (3): 265–293, doi:10.1007/BF02293049, MR 1174358, S2CID 30101649 <a href="/wiki/Subhash_Suri" target="_blank">/wiki/Subhash_Suri</a> <a href="#fnref:86" class="footnote-back-ref">↩</a></li>
<li id="fn:87">Eades, Peter; Whitesides, Sue (1996), "The realization problem for Euclidean minimum spanning trees is NP-hard", Algorithmica, 16 (1): 60–82, doi:10.1007/s004539900037, MR 1394494 <a href="/wiki/Peter_Eades" target="_blank">/wiki/Peter_Eades</a> <a href="#fnref:87" class="footnote-back-ref">↩</a></li>
<li id="fn:88">Monma, Clyde; Suri, Subhash (1992), "Transitions in geometric minimum spanning trees", Discrete & Computational Geometry, 8 (3): 265–293, doi:10.1007/BF02293049, MR 1174358, S2CID 30101649 <a href="/wiki/Subhash_Suri" target="_blank">/wiki/Subhash_Suri</a> <a href="#fnref:88" class="footnote-back-ref">↩</a></li>
<li id="fn:89">King, James A. (2006), "Realization of degree 10 minimum spanning trees in 3-space" (PDF), Proceedings of the 18th Annual Canadian Conference on Computational Geometry, CCCG 2006, August 14-16, 2006, Queen's University, Ontario, Canada, pp. 39–42 <a href="https://www.cs.queensu.ca/cccg/papers/cccg11.pdf" target="_blank">https://www.cs.queensu.ca/cccg/papers/cccg11.pdf</a> <a href="#fnref:89" class="footnote-back-ref">↩</a></li>
<li id="fn:90">Angelini, Patrizio; Bruckdorfer, Till; Chiesa, Marco; Frati, Fabrizio; Kaufmann, Michael; Squarcella, Claudio (2014), "On the area requirements of Euclidean minimum spanning trees", Computational Geometry: Theory and Applications, 47 (2, part B): 200–213, doi:10.1016/j.comgeo.2012.10.011, MR 3123788 <a href="/wiki/Computational_Geometry_(journal)" target="_blank">/wiki/Computational_Geometry_(journal)</a> <a href="#fnref:90" class="footnote-back-ref">↩</a></li>
<li id="fn:91">Frati, Fabrizio; Kaufmann, Michael (2011), "Polynomial area bounds for MST embeddings of trees", Computational Geometry: Theory and Applications, 44 (9): 529–543, doi:10.1016/j.comgeo.2011.05.005, MR 2819643, S2CID 5634139 <a href="/wiki/Computational_Geometry_(journal)" target="_blank">/wiki/Computational_Geometry_(journal)</a> <a href="#fnref:91" class="footnote-back-ref">↩</a></li>
</ol>

Euclidean minimum spanning tree open-in-new

Euclidean minimum spanning tree