Целые точки в выпуклых многогранниках - Integer points in convex polyhedra

Красные точки - это целые точки решетки внутри синего многоугольника, последний представляет собой двумерный линейная программа

Изучение целые точки в выпуклых многогранниках[1] мотивируется такими вопросами, как "сколько неотрицательных целое число -ценные решения система линейных уравнений с неотрицательными коэффициентами имеет "или" сколько решений имеет целочисленная линейная программа иметь ". Подсчет целых точек в многогранники или другие вопросы о них возникают в теория представлений, коммутативная алгебра, алгебраическая геометрия, статистика, и Информатика.[2]

Набор целочисленных точек или, в более общем смысле, набор точек аффинная решетка, в многограннике называется Z-многогранник,[3] из математической записи или же Z для набора целых чисел.[4]

Характеристики

Для решетки Λ Теорема Минковского связывает число d (Λ) и объем симметричной выпуклый набор S количеству узлов решетки, содержащихся в S.

Количество узлов решетки, содержащихся в многогранник все вершины которого являются элементами решетки, описывается многогранником Многочлен Эрхарта. В формулах для некоторых коэффициентов этого многочлена входит также d (Λ).

Приложения

Оптимизация цикла

В определенных подходах к оптимизация цикла, набор выполнений тела цикла рассматривается как набор целочисленных точек в многограннике, определяемом ограничениями цикла.

Смотрите также

Ссылки и примечания

  1. ^ В некоторых случаях выпуклые многогранники называются просто «многогранниками».
  2. ^ Целые точки в многогранниках. Геометрия, теория чисел, теория представлений, алгебра, оптимизация, статистика, Совместная летняя научная конференция ACM - SIAM, 2006 г.
  3. ^ Термин «Z-многогранник» также используется как синоним к выпуклый решетчатый многогранник, то выпуклый корпус конечного числа точек аффинной решетки.
  4. ^ «Вычисления на итерированных пространствах» в: Справочник по проектированию компиляторов: Оптимизация и генерация машинного кода, CRC Press 2007, 2-е издание, ISBN  1-4200-4382-X, стр.15-7

дальнейшее чтение