Целовыпуклое множество

Целочисленно -выпуклое множество является дискретным геометрическим аналогом понятия выпуклого множества в геометрии.

Подмножество X целочисленной сетки $\mathbb {Z} ^{n}$ является целочисленно выпуклой, если любая точка y в выпуклой оболочке X может быть выражена как выпуклая комбинация точек X , которые находятся «рядом» y , где «рядом» означает, что расстояние между каждыми двумя координатами меньше 1. ^[1]

Определения

Пусть X — подмножество $\mathbb {Z} ^{n}$ .

Обозначим через ch( ) выпуклую оболочку X . X Обратите внимание, что ch( X ) является подмножеством $\mathbb {R} ^{n}$ , поскольку он содержит все действительные точки, которые являются выпуклыми комбинациями целых точек из X .

Для любой точки y в $\mathbb {R} ^{n}$ , обозначим close( y ) := { z в $\mathbb {Z} ^{n}$ | | z _я - y _я | < 1 для всех i в {1,..., n } }. Это целочисленные точки, которые считаются «ближайшими» к реальной точке y .

Подмножество X $\mathbb {Z} ^{n}$ называется цело-выпуклой , если каждая точка y из ch( X ) также находится в ch( X ∩ close( y )). ^[2]

Пример

Пусть n = 2 и X = { (0,0), (1,0), (2,0), (2,1) }. Его выпуклая оболочка ch( X ) содержит, например, точку y = (1.2, 0.5).

Целочисленные точки рядом с y — это close( y ) = {(1,0), (2,0), (1,1), (2,1) }. Итак, X ∩ close( y ) = {(1,0), (2,0), (2,1)}. Но y не находится в ch( X ∩ Near( y )). См. изображение справа.

Следовательно, X не целочисленно выпукло. ^[1]

Напротив, множество Y = { (0,0), (1,0), (2,0), (1,1), (2,1) } цело-выпуклое.

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

Иимура, Мурота и Тамура ^[3] показали следующее свойство целовыпуклого множества.

Позволять $X\subset \mathbb {Z} ^{n}$ — конечное целовыпуклое множество. Существует целая ch ( X ) триангуляция , т.е.:

Вершины триангуляции — это вершины X ;
Вершины каждого симплекса триангуляции лежат в одной и той же «ячейке» (гиперкубе со стороной 1) целочисленной сетки. $\mathbb {Z} ^{n}$ .

Набор примеров X не является цело-выпуклым, и действительно, ch( X ) не допускает целочисленной триангуляции: каждая триангуляция ch( X ) либо должна добавлять вершины, не входящие в X , либо должна включать симплексы, которые не содержатся в одна ячейка.

Напротив, множество Y = { (0,0), (1,0), (2,0), (1,1), (2,1) } целочисленно выпукло и действительно допускает целочисленную триангуляцию, например с тремя симплексами {(0,0),(1,0),(1,1)} и {(1,0),(2,0),(2,1)} и {(1,0) ,(1,1),(2,1)}. См. изображение справа.

Ссылки

^ Jump up to: ^а ^б Ян, Зайфу (1 декабря 2009 г.). «Дискретный анализ с фиксированной точкой и его приложения». Журнал теории и приложений с фиксированной точкой . 6 (2): 351–371. дои : 10.1007/s11784-009-0130-9 . ISSN 1661-7746 . S2CID 122640338 .
^ Чен, Си; Дэн, Сяоте (2006). «Симплициальный подход к дискретным теоремам о неподвижной точке». В Чене, Дэнни З.; Ли, DT (ред.). Вычисления и комбинаторика . Конспекты лекций по информатике. Том. 4112. Берлин, Гейдельберг: Springer. стр. 3–12. дои : 10.1007/11809678_3 . ISBN 978-3-540-36926-4 .
^ Иимура, Такуя; Мурота, Кадзуо; Тамура, Акихиса (1 декабря 2005 г.). «Пересмотр теоремы о дискретной неподвижной точке» (PDF) . Журнал математической экономики . 41 (8): 1030–1036. дои : 10.1016/j.jmateco.2005.03.001 . ISSN 0304-4068 .

[:1-1] Jump up to: ^а ^б Ян, Зайфу (1 декабря 2009 г.). «Дискретный анализ с фиксированной точкой и его приложения». Журнал теории и приложений с фиксированной точкой . 6 (2): 351–371. дои : 10.1007/s11784-009-0130-9 . ISSN 1661-7746 . S2CID 122640338 .

[2] Чен, Си; Дэн, Сяоте (2006). «Симплициальный подход к дискретным теоремам о неподвижной точке». В Чене, Дэнни З.; Ли, DT (ред.). Вычисления и комбинаторика . Конспекты лекций по информатике. Том. 4112. Берлин, Гейдельберг: Springer. стр. 3–12. дои : 10.1007/11809678_3 . ISBN 978-3-540-36926-4 .

[3] Иимура, Такуя; Мурота, Кадзуо; Тамура, Акихиса (1 декабря 2005 г.). «Пересмотр теоремы о дискретной неподвижной точке» (PDF) . Журнал математической экономики . 41 (8): 1030–1036. дои : 10.1016/j.jmateco.2005.03.001 . ISSN 0304-4068 .

[1]

[2]

[3]