Concept

Greedy algorithm

A rule that repeatedly makes the choice which looks best at the moment and never reconsiders. It gives the true optimum for problems with a matroid structure, such as the minimum spanning tree, and only an approximation for most others.

Named by 2 essays across 2 fields — each of them below, with the objects they name alongside it.

6 necklaces, concatenated into a de Bruijn sequence. The Lyndon words of length dividing 4 over 2 letters, listed in lexicographic order and written end to end; the result is the lexicographically least de Bruijn sequence of order 4.

Every necklace, in order

The graph construction needs the whole graph in memory and finds one sequence among hundreds of millions. Listing the necklaces in alphabetical order and writing them end to end needs no graph at all, and produces the smallest of them.

computation · De bruijn

The shortest tree was already in the triangulation. The Delaunay triangulation of 20 sites in faint lines with the minimum spanning tree drawn over it in heavy ones. Every tree edge is a triangulation edge, and the circles on the longest few tree edges as diameters contain no other site.

The tree inside the triangulation

The shortest network joining a set of points is built from edges chosen by length, and the triangulation is built from edges chosen by an emptiness condition about circles. The two constructions share no step, and every edge of the first is an edge of the second.

geometry · Voronoi

Named alongside it

The objects these essays reach for when they reach for this one.

Circumcircle Complexity Counting argument De bruijn sequence Delaunay triangulation Equivalence class Eulerian path Graph Lexicographic order Lyndon word Necklace Planar graph

All concepts