Диаграмма Гейла
В полиэдральной комбинаторике преобразование Гейла превращает вершины любых выпуклых многогранников в набор векторов или точек в пространстве другой размерности, диаграмму Гейла многогранника. Его можно использовать для описания многогранников высокой размерности с небольшим количеством вершин путем преобразования их в наборы точек в пространстве гораздо меньшей размерности. Этот процесс также можно обратить вспять, чтобы построить многогранники с желаемыми свойствами из их диаграмм Гейла. Преобразование Гейла и диаграмма Гейла названы в честь Дэвида Гейла , который представил эти методы в статье 1956 года о многогранниках-соседях . [1]
Учитывая -мерный многогранник с вершинами, присоедините 1 к декартовым координатам каждой вершины, чтобы получить -мерный вектор-столбец . Матрица этих вектор - столбцов имеет размеры и ранг . Преобразование Гейла заменяет эту матрицу матрицей размерности , векторы-столбцы которой являются основой для ядра . Затем имеет векторы-строки размерности . Эти векторы-строки образуют диаграмму Гейла многогранника. Есть выбор, какой базис использовать для ядра, но он меняет результат только линейным преобразованием. [2]
Собственное подмножество вершин многогранника образует множество вершин грани многогранника тогда и только тогда, когда дополнительное множество векторов преобразования Гейла имеет выпуклую оболочку , содержащую начало координат в своей относительной внутренней части . [3] Эквивалентно, подмножество вершин образует грань тогда и только тогда, когда не существует линейной функции, которая присваивает неотрицательные значения дополнительным векторам. [4]
Поскольку преобразование Гейла определено только до линейного преобразования, его ненулевые векторы могут быть нормализованы ко всем -мерным единичным векторам . Линейная диаграмма Гейла — это нормализованная версия преобразования Гейла, в которой все векторы равны нулю или единичным векторам. [5]
