Диаграмма Вороного
Разбиение плоскости на ячейки по одной на каждую опорную точку: в ячейке лежит всё, что к своей точке ближе, чем к любой другой.
Названа в честь Георгия Вороного (1908), хотя набросал эту идею ещё Декарт. Для заданного набора опорных точек каждое место относят к ближайшей из них, и пространство нарезается на выпуклые ячейки. Диаграмма двойственна триангуляции Делоне: соедините точки, чьи ячейки имеют общее ребро, — и получите одну из другой.
Игры пользуются ею постоянно: карты биомов и регионов, узоры трещин и осколков для разрушаемой геометрии, процедурные текстуры (шум Уорли — это просто расстояние Вороного) и карты влияния. Заметающая прямая Фортуна строит её за O(n log n).