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

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

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

Набор целочисленных точек или, в более общем смысле, набор точек аффинная решетка, в многограннике называется Z-многогранник,^[3] из математической записи ${\displaystyle \mathbb {Z} }$ или же 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

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

• Барвинок Александр; Бек, Матиас; Хаасе, Кристиан; Резник, Брюс; Велкер, Фолькмар (2005), Целочисленные точки в многогранниках: материалы совместной летней исследовательской конференции AMS-IMS-SIAM, проходившей в Сноуберд, штат Юта, 13–17 июля 2003 г., Современная математика, 374, Провиденс, Род-Айленд: Американское математическое общество, Дои:10,1090 / conm / 374, ISBN  0-8218-3459-2, МИСТЕР  2134757
• Барвинок Александр (2008), Целые точки в многогранниках, Цюрихские лекции по высшей математике, Цюрих: Европейское математическое общество, Дои:10.4171/052, ISBN  978-3-03719-052-4, МИСТЕР  2455889
• Бек, Матиас; Хаасе, Кристиан; Резник, Брюс; Вернь, Мишель; Велкер, Фолькмар; Ёсида, Рюрико (2008), Целые точки в многогранниках: геометрия, теория чисел, теория представлений, алгебра, оптимизация, статистика (PDF), Современная математика, 452, Провиденс, Род-Айленд: Американское математическое общество, Дои:10,1090 / conm / 452, ISBN  978-0-8218-4173-0, МИСТЕР  2416261