Euclidean minimum spanning tree (original) (raw)
A Euclidean minimum spanning tree of a finite set of points in the Euclidean plane or higher-dimensional Euclidean space connects the points by a system of line segments with the points as endpoints, minimizing the total length of the segments. In it, any two points can reach each other along a path through the line segments. It can be found as the minimum spanning tree of a complete graph with the points as vertices and the Euclidean distances between points as edge weights.
| Property | Value |
|---|---|
| dbo:abstract | A Euclidean minimum spanning tree of a finite set of points in the Euclidean plane or higher-dimensional Euclidean space connects the points by a system of line segments with the points as endpoints, minimizing the total length of the segments. In it, any two points can reach each other along a path through the line segments. It can be found as the minimum spanning tree of a complete graph with the points as vertices and the Euclidean distances between points as edge weights. The edges of the minimum spanning tree meet at angles of at least 60°, at most six to a vertex. In higher dimensions, the number of edges per vertex is bounded by the kissing number of tangent unit spheres. The total length of the edges, for points in a unit square, is at most proportional to the square root of the number of points. Each edge lies in an empty region of the plane, and these regions can be used to prove that the Euclidean minimum spanning tree is a subgraph of other geometric graphs including the relative neighborhood graph and Delaunay triangulation. By constructing the Delaunay triangulation and then applying a graph minimum spanning tree algorithm, the minimum spanning tree of given planar points may be found in time , as expressed in big O notation. This is optimal in some models of computation, although faster randomized algorithms exist for points with integer coordinates. For points in higher dimensions, finding an optimal algorithm remains an open problem. (en) Евклидово минимальное остовное дерево (англ. Euclidean minimum spanning tree, EMST) — это минимальное остовное дерево набора из n точек на плоскости (или более обще, в ), где вес ребра между любой парой точек является евклидовым расстоянием между двумя точками. Простыми терминами, EMST связывает набор точек с помощью отрезков так, что общая длина всех отрезков минимальна и любая точка может быть достигнута из другой точки по этим отрезкам. На плоскости EMST для данного набора точек может быть найдено за время Θ(n log n) с использованием пространства O(n) при вычислении модели . Известны более быстрые вероятностные алгоритмы со сложностью в более сильных моделях вычисления, которые более точно моделируют возможности реальных компьютеров. В более высоких размерностях поиск оптимального алгоритма остаётся открытой проблемой. (ru) Евклі́дове мініма́льне кістяко́ве де́рево (ЕМКД; англ. Euclidean minimum spanning tree, EMST) — це мінімальне кістякове дерево набору з n точок на площині (або загальніше, ), де вага ребра між будь-якою парою точок є евклідовою відстанню між двома точками. Простими термінами ЕМКД пов'язує набір точок за допомогою відрізків так, що загальна довжина всіх відрізків мінімальна і будь-яку точку можна досягти з іншої точки за цими відрізками. На площині ЕМКД для даного набору точок можна знайти за час з використанням простору при обчисленні моделі алгебричного дерева розв'язків. У сильніших моделях обчислення, які точніше моделюють можливості реальних комп'ютерів, відомі швидші ймовірнісні алгоритми зі складністю . У вищих розмірностях пошук оптимального алгоритму залишається відкритою проблемою. (uk) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Euclidean_minimum_spanning_tree.svg?width=300 |
| dbo:wikiPageExternalLink | https://mlpack.org/doc/stable/doxygen/emst_tutorial.html |
| dbo:wikiPageID | 1040597 (xsd:integer) |
| dbo:wikiPageLength | 55513 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1112222220 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Prim's_algorithm dbr:Electrical_grid dbr:Euclidean_traveling_salesman_problem dbr:Bitwise_operation dbr:Algorithm_engineering dbr:Almost_surely dbc:Spanning_tree dbc:Geometric_graphs dbr:Regular_hexagon dbr:Regular_polygon dbr:Rhombus dbr:Degree_(graph_theory) dbr:Delaunay_triangulation dbr:Line_segment dbr:Complete_graph dbr:Geographic_information_science dbr:Geometric_spanner dbr:Online_algorithm dbr:South_Moravian_Region dbr:Mixture_model dbr:Equilateral_triangle dbr:Galaxy dbr:Mlpack dbr:NP-hard dbr:Convex_hull dbr:Lens_(geometry) dbr:Linear_time dbr:Lp_space dbr:Shortest_path_problem dbr:Simplex dbr:Star_(graph_theory) dbr:Steiner_tree_problem dbr:Closest_pair_of_points_problem dbr:Kruskal's_algorithm dbr:Particle_physics dbr:Polygon dbr:Unit_sphere dbr:Cauchy–Schwarz_inequality dbr:Travelling_salesman_problem dbr:Tree_(graph_theory) dbr:Dark_matter_halo dbr:Davenport–Schinzel_sequence dbr:Well-separated_pair_decomposition dbr:Gabriel_graph dbr:Laplace_distribution dbr:Local_feature_size dbr:Wireless_ad_hoc_network dbr:Open_problem dbr:Euclidean_space dbr:Finite_set dbr:Broadcasting_(networking) dbr:Iterated_logarithm dbr:Kinetic_Euclidean_minimum_spanning_tree dbr:Kinetic_data_structure dbr:Rectilinear_minimum_spanning_tree dbr:Steiner_ratio dbr:Big_O_notation dbr:Hierarchical_clustering dbr:Taxicab_geometry dbr:Yao_graph dbr:Single-linkage_clustering dbr:Borůvka's_algorithm dbr:Planar_graph dbr:Square_root dbr:Greedy_geometric_spanner dbr:Minimum_spanning_tree dbr:Bubble_chamber dbr:Randomized_algorithm dbr:Randomized_algorithms dbr:Kissing_number dbr:Array_index dbr:Relative_neighborhood_graph dbr:Unit_square dbr:Vesica_piscis dbr:Euclidean_distance dbr:Euclidean_plane dbr:Expected_linear_time_MST_algorithm dbr:Moving_least_squares dbr:Urquhart_graph dbr:Polygonal_chain dbr:Polygonalization dbr:Random_access dbr:Polynomial_time_approximation_scheme dbr:Connected_set dbr:Constant-factor_approximation_algorithm dbr:Geometric_graph dbr:Algebraic_decision_tree dbr:File:Kissing-3d.png dbr:Algebraic_computation_tree dbr:File:EMST_empty_regions.svg dbr:File:Euclidean_minimum_spanning_tree.svg |
| dbp:wikiPageUsesTemplate | dbt:Good_article dbt:Math dbt:R dbt:Reflist dbt:Short_description dbt:Bi |
| dct:subject | dbc:Spanning_tree dbc:Geometric_graphs |
| gold:hypernym | dbr:Tree |
| rdf:type | yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Communication100033020 yago:Event100029378 yago:Graph107000195 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:WikicatGeometricGraphs yago:YagoPermanentlyLocatedEntity dbo:Plant yago:Rule105846932 yago:VisualCommunication106873252 yago:WikicatAlgorithms |
| rdfs:comment | A Euclidean minimum spanning tree of a finite set of points in the Euclidean plane or higher-dimensional Euclidean space connects the points by a system of line segments with the points as endpoints, minimizing the total length of the segments. In it, any two points can reach each other along a path through the line segments. It can be found as the minimum spanning tree of a complete graph with the points as vertices and the Euclidean distances between points as edge weights. (en) Евклидово минимальное остовное дерево (англ. Euclidean minimum spanning tree, EMST) — это минимальное остовное дерево набора из n точек на плоскости (или более обще, в ), где вес ребра между любой парой точек является евклидовым расстоянием между двумя точками. Простыми терминами, EMST связывает набор точек с помощью отрезков так, что общая длина всех отрезков минимальна и любая точка может быть достигнута из другой точки по этим отрезкам. В более высоких размерностях поиск оптимального алгоритма остаётся открытой проблемой. (ru) Евклі́дове мініма́льне кістяко́ве де́рево (ЕМКД; англ. Euclidean minimum spanning tree, EMST) — це мінімальне кістякове дерево набору з n точок на площині (або загальніше, ), де вага ребра між будь-якою парою точок є евклідовою відстанню між двома точками. Простими термінами ЕМКД пов'язує набір точок за допомогою відрізків так, що загальна довжина всіх відрізків мінімальна і будь-яку точку можна досягти з іншої точки за цими відрізками. У вищих розмірностях пошук оптимального алгоритму залишається відкритою проблемою. (uk) |
| rdfs:label | Euclidean minimum spanning tree (en) Евклидово минимальное остовное дерево (ru) Евклідове мінімальне кістякове дерево (uk) |
| owl:sameAs | freebase:Euclidean minimum spanning tree yago-res:Euclidean minimum spanning tree wikidata:Euclidean minimum spanning tree dbpedia-fa:Euclidean minimum spanning tree dbpedia-ru:Euclidean minimum spanning tree dbpedia-sr:Euclidean minimum spanning tree dbpedia-th:Euclidean minimum spanning tree dbpedia-uk:Euclidean minimum spanning tree https://global.dbpedia.org/id/48QKU |
| prov:wasDerivedFrom | wikipedia-en:Euclidean_minimum_spanning_tree?oldid=1112222220&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Kissing-3d.png wiki-commons:Special:FilePath/EMST_empty_regions.svg wiki-commons:Special:FilePath/Euclidean_minimum_spanning_tree.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Euclidean_minimum_spanning_tree |
| is dbo:wikiPageDisambiguates of | dbr:Spanning_tree_(disambiguation) dbr:EMST |
| is dbo:wikiPageRedirects of | dbr:Algorithms_for_finding_Euclidean_minimum_spanning_trees_in_two_dimensions dbr:Euclidean_Minimum_Spanning_Tree dbr:Sample_Code_for_Euclidean_MST_using_Boost_and_CGAL |
| is dbo:wikiPageWikiLink of | dbr:Proximity_problems dbr:List_of_algorithms dbr:Beta_skeleton dbr:List_of_books_in_computational_geometry dbr:Delaunay_triangulation dbr:Geometric_graph_theory dbr:Nearest_neighbor_graph dbr:Mlpack dbr:Spanning_tree dbr:Spanning_tree_(disambiguation) dbr:Avner_Magen dbr:Travelling_salesman_problem dbr:Well-separated_pair_decomposition dbr:Widest_path_problem dbr:Gabriel_graph dbr:Algorithms_for_finding_Euclidean_minimum_spanning_trees_in_two_dimensions dbr:Euclidean_Minimum_Spanning_Tree dbr:Iterated_logarithm dbr:Kinetic_Euclidean_minimum_spanning_tree dbr:List_of_NP-complete_problems dbr:Rectilinear_minimum_spanning_tree dbr:EMST dbr:Yao_graph dbr:Greedy_geometric_spanner dbr:Minimum_spanning_tree dbr:Relative_neighborhood_graph dbr:Gilbert–Pollack_conjecture dbr:Urquhart_graph dbr:Sample_Code_for_Euclidean_MST_using_Boost_and_CGAL |
| is foaf:primaryTopic of | wikipedia-en:Euclidean_minimum_spanning_tree |
