Euclidean minimum spanning tree

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. A Euclidean minimum spanning tree, for a set of points in the Euclidean plane or Euclidean space, is a system of line segments, having only the given points as their endpoints, whose union includes all of the points in a connected set, and which has the minimum possible total length of any such system. Such a network cannot contain a polygonal 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 tree.

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications (1)

Related concepts (7)

Related courses (7)

Related lectures (68)

Euclidean minimum spanning tree

Geometric spanner

A geometric spanner or a t-spanner graph or a t-spanner was initially introduced as a weighted graph over a set of points as its vertices for which there is a t-path between any pair of vertices for a fixed parameter t. A t-path is defined as a path through the graph with weight at most t times the spatial distance between its endpoints. The parameter t is called the stretch factor or dilation factor of the spanner. In computational geometry, the concept was first discussed by L.P.

Beta skeleton

In computational geometry and geometric graph theory, a β-skeleton or beta skeleton is an undirected graph defined from a set of points in the Euclidean plane. Two points p and q are connected by an edge whenever all the angles prq are sharper than a threshold determined from the numerical parameter β. Let β be a positive real number, and calculate an angle θ using the formulas For any two points p and q in the plane, let Rpq be the set of points for which angle prq is greater than θ.

MATH-434: Lattice models

Lattice models consist of (typically random) objects living on a periodic graph. We will study some models that are mathematically interesting and representative of physical phenomena seen in the real

CS-450: Algorithms II

A first graduate course in algorithms, this course assumes minimal background, but moves rapidly. The objective is to learn the main techniques of algorithm analysis and design, while building a reper

MATH-360: Graph theory

The course aims to introduce the basic concepts and results of modern Graph Theory with special emphasis on those topics and techniques that have proved to be applicable in theoretical computer scienc

Inhomogeneous minima of mixed signature lattices

Eva Bayer Fluckiger, Martino Borello, Peter Simon Jossen

We establish an explicit upper bound for the Euclidean minimum of a number field which depends, in a precise manner, only on its discriminant and the number of real and complex embeddings. Such bounds were shown to exist by Davenport and Swinnerton-Dyer ([9-11]). In the case of totally real fields, an optimal bound was conjectured by Minkowski and it is proved for fields of small degree. In this note we develop methods of McMullen ([20]) in the case of mixed signature in order to get explicit bounds for the Euclidean minimum. (C) 2016 Elsevier Inc. All rights reserved.

Academic Press Inc Elsevier Science2016

Maximizing Candies in a City CS-250: Algorithms I

Explores maximizing candies in a city, dynamic programming, minimum spanning trees, and stock price prediction strategies.

Traveling Salesman Problem: Resolution Algorithms CS-119(a): Information, Computation, Communication MOOC: Information, Calcul, Communication: Introduction à la pensée informatique

Explores the Traveling Salesman Problem, resolution algorithms, minimum spanning tree, and shortcut optimization.

Slabs: Design and Pre-dimensioning CIVIL-123: Structures II

Covers pre-dimensioning and graphical representation of slabs supported by beams and columns.