Algorithms

Euclidean, Voronoi graph, and convex hull.

Given set S of points in the Euclidean plane, Voronoi graph of S always Contains MST of S Yes No Don't know Has at most 3.16*|S| edges Yes No Don't know Has at most 3.1*|S| edges Yes No Don't know Has at most 2.75*|S| edges Yes No Don't know Has at most 2.85*|S| edges Yes No Don't know Has at least |S| edges Yes No Don't know Has at least |S|+1 edges Yes No Don't know Contains edge connecting closest pair of points Yes No Don't know Given set S of points in the Euclidean plane, convex hull of S always Contains MST of S Yes No Don't know Has at most 2.5*|S| edges Yes No Don't know Has at least 1.05*|S| edges Yes No Don't know Contains edge connecting closest pair of points Yes No Don't know