Функция сохранения направления - Direction-preserving function

В дискретная математика, а функция сохранения направления (или отображение) - это функция в дискретном пространстве, таком как целочисленная сетка, которая (неформально) не меняется слишком сильно между двумя соседними точками. Его можно рассматривать как дискретный аналог непрерывная функция.

Концепция была впервые определена Иимурой.^[1][2] Некоторые варианты этого позже были определены Яном,^[3] Чен и Дэн,^[4] Херингс, ван-дер-Лаан, Талман и Ян,^[5] и другие.

Базовые концепты

Делаем упор на функции ${ displaystyle f: X to mathbb {R} ^ {n}}$, где область X - конечное подмножество евклидова пространства ${ Displaystyle mathbb {R} ^ {п}}$. ch (Икс) обозначает выпуклый корпус из Икс.

Есть много вариантов свойств сохранения направления, в зависимости от того, как точно определить «резкое изменение» и «соседние точки». По поводу «кардинального изменения» есть два основных варианта:

• Сохранение направления (DP) означает, что если Икс и y смежны, то для всех ${ Displaystyle я в [п]}$: ${ Displaystyle е_ {я} (х) cdot f_ {я} (у) geq 0}$. Прописью: каждый компонент функции ж нельзя переключать знаки между соседними точками.
• Сохранение общего направления (ВВП) означает, что если Икс и y смежны, то ${ Displaystyle е (х) CDOT е (у) geq 0}$. На словах: направление функции ж (как вектор) не изменяется более чем на 90 градусов между соседними точками. Обратите внимание, что DP подразумевает ВВП, но не наоборот.

По поводу «соседних точек» есть несколько вариантов:

• Гиперкубический Значит это Икс и y смежны тогда и только тогда, когда они содержатся в некотором параллельном осям гиперкубе со стороной 1.
• Симплициальный Значит это Икс и y смежны тогда и только тогда, когда они являются вершинами одного симплекса в некоторой триангуляции области. Обычно симплициальная смежность намного сильнее гиперкубической смежности; соответственно, гиперкубическая ДП намного сильнее симплициальной ДП.

Конкретные определения представлены ниже. Все примеры ниже предназначены для ${ displaystyle n = 2}$ размеры и для Икс = { (2,6), (2,7), (3, 6), (3, 7) }.

Свойства и примеры

Сохранение гиперкубического направления

А клетка это подмножество ${ Displaystyle mathbb {R} ^ {п}}$ что может быть выражено ${ Displaystyle к + [0,1] ^ {п}}$ для некоторых ${ Displaystyle к ин mathbb {Z} ^ {п}}$. Например, квадрат ${ Displaystyle [2,3] раз [6,7]}$ это клетка.

Две точки в ${ Displaystyle mathbb {R} ^ {п}}$ называются ячейка подключена если есть ячейка, содержащая их обоих.

Свойства сохранения гиперкубического направления требуют, чтобы функция не изменялась слишком резко в точках, связанных с ячейками (точках в той же гиперкубической ячейке).

жа	6	7
2	(2,1)	(1,1)
3	(0,1)	(0,0)

ж называется гиперкубическое направление с сохранением (HDP) если для любой пары точек, соединенных ячейками Икс,y в ИКС, для всех ${ Displaystyle я в [п]}$: ${ Displaystyle е_ {я} (х) cdot f_ {я} (у) geq 0}$. Период, термин локально с сохранением направления (LDP) вместо этого часто используется.^[1] Функция ж^а справа ДП.

• Некоторые авторы^[4]:Def.1 используйте вариант, требующий этого, для любой пары точек, соединенных ячейками Икс,y в ИКС, для всех ${ Displaystyle я в [п]}$: ${ Displaystyle (е_ {я} (х) -x_ {я}) cdot (f_ {я} (у) -y_ {я}) geq 0}$. Функция ж(Икс) является HDP по второму варианту, если функция грамм(Икс):=ж(Икс)-Икс это HDP по первому варианту.

жб	6	7
2	(2,1)	(1,1)
3	(1,-1)	(0,0)

ж называется гиперкубическое сохранение направления (HGDP), или же локально валовое сохранение направления (LGDP), если для любой пары клеточно-связанных точек Икс,y в ИКС, ${ Displaystyle е (х) CDOT е (у) geq 0}$.^{[3]:По умолчанию 2.2} Каждая функция HDP является HGDP, но обратное неверно. Функция ж^б - это HGDP, поскольку скалярное произведение каждых двух векторов в таблице неотрицательно. Но это не HDP, поскольку второй компонент переключает знак между (2,6) и (3,6): ${ displaystyle f_ {2} ^ {b} (2,6) cdot f_ {2} ^ {b} (3,6) = - 1 <0}$.

• Некоторые авторы^[5] используйте вариант, требующий этого, для любой пары точек, соединенных ячейками Икс,y в ИКС, ${ Displaystyle (е (х) -x) cdot (f (y) -y) geq 0}$. Функция ж(Икс) является HGDP по второму варианту, если функция грамм(Икс):=ж(Икс)-Икс это HGDP по первому варианту.

Симплициальное сохранение направления

А симплекс называется интеграл если все его вершины имеют целочисленные координаты и все они лежат в одной ячейке (то есть разница между координатами разных вершин не больше 1).

А триангуляция некоторого подмножества ${ Displaystyle mathbb {R} ^ {п}}$ называется интеграл если все его симплексы целые.

Учитывая триангуляцию, две точки называются симплициально связанный если существует симплекс триангуляции, содержащий их обоих.

Обратите внимание, что в интегральной триангуляции все симплициально-связанные точки также являются клеточно-связными, но обратное неверно. Например, рассмотрим ячейку ${ Displaystyle [2,3] раз [6,7]}$. Рассмотрим интегральную триангуляцию, которая разбивает его на два треугольника: {(2,6), (2,7), (3,7)} и {(2,6), (3,6), (3,7)} . Точки (2,7) и (3,6) клеточно-связны, но не симплициально связаны.

Симплициальные свойства сохранения направления предполагают некоторую фиксированную интегральную триангуляцию входной области. Они требуют, чтобы функция не изменялась слишком резко в симплициально-связанных точках (точках в одном симплексе триангуляции). Это, как правило, гораздо более слабое требование, чем сохранение гиперкубического направления.

ж называется симплициальное сохранение направления (SDP) если для некоторой интегральной триангуляции Икс, для любой пары симплициально-связанных точек Икс,y в ИКС, для всех ${ Displaystyle я в [п]}$: ${ Displaystyle (е_ {я} (х) -x_ {я}) cdot (f_ {я} (у) -y_ {я}) geq 0}$.^[4]:Def.4

жc	6	7
2	(2,1)	(1,1)
3	(1,-2)	(0,0)

ж называется симплициально грубое сохранение направления (SGDP) или же симплициально-локальное сохранение общего направления (SLGDP) если существует целая триангуляция ch (Икс) такое, что для любой пары симплициально-связанных точек Икс,y в ИКС, ${ Displaystyle е (х) CDOT е (у) geq 0}$.^[6][7][8]

Каждая функция HGDP - это SGDP, но HGDP намного сильнее: он эквивалентен SGDP w.r.t. все возможное интегральные триангуляции ch (Икс), тогда как SGDP относится к Один триангуляция.^{[3]:По умолчанию 2.3} Например, функция ж^c справа - SGDP посредством триангуляции, которая делит ячейку на два треугольника {(2,6), (2,7), (3,7)} и {(2,6), (3,6), ( 3,7)}, поскольку в каждом треугольнике скалярное произведение каждых двух векторов неотрицательно. Но это не HGDP, поскольку ${ displaystyle f ^ {c} (3,6) cdot f ^ {c} (2,7) = - 1 <0}$.

Рекомендации