| 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)
|
| 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)
|