Ортогональная выпуклая оболочка

В геометрии множество $K \subset R д$ определяется как ортогонально выпуклый , если для каждой линии $L$ параллельной одному из стандартных базисных векторов, пересечение K $,$ с $L$ является пустым, точкой или одним сегментом . Термин «ортогональный» относится к соответствующему декартову базису и координатам в евклидовом пространстве , где различные базисные векторы перпендикулярны , а также к соответствующим прямым. В отличие от обычных выпуклых множеств , ортогонально выпуклое множество не обязательно связно .

Ортогональная выпуклая оболочка множества $K \subset R д$ является пересечением всех связных ортогонально выпуклых надмножеств $K$ .

Эти определения сделаны по аналогии с классической теорией выпуклости, в которой $K$ является выпуклым , если для каждой прямой $L$ пересечение $K$ с $L$ пусто, является точкой или единственным отрезком. Ортогональная выпуклость ограничивает линии, для которых должно соблюдаться это свойство, поэтому каждое выпуклое множество ортогонально выпукло, но не наоборот. По той же причине ортогональная выпуклая оболочка сама по себе является подмножеством выпуклой оболочки того же множества точек. Точка $p$ принадлежит ортогональной выпуклой оболочке $K$ тогда и только тогда, когда каждый из замкнутых ортантов, ориентированных по оси, имеющих $p$ в качестве вершины, имеет непустое пересечение с $K$ .

Ортогональная выпуклая оболочка также известна как прямолинейная выпуклая оболочка или, в двух измерениях , $x$ - $y$ выпуклая оболочка .

Пример

На рисунке показан набор из 16 точек на плоскости и ортогональная выпуклая оболочка этих точек. Как видно на рисунке, ортогональная выпуклая оболочка представляет собой многоугольник с некоторыми вырожденными ребрами, соединяющими крайние вершины в каждом координатном направлении. Для дискретного набора точек, такого как этот, все ортогональные края выпуклой оболочки горизонтальны или вертикальны. В этом примере ортогональная выпуклая оболочка связна.

Альтернативные определения

В отличие от классической выпуклости, где существует несколько эквивалентных определений выпуклой оболочки, определения ортогональной выпуклой оболочки, сделанные по аналогии с определениями выпуклой оболочки, приводят к различным геометрическим объектам. На данный момент исследователи исследовали следующие четыре определения ортогональной выпуклой оболочки множества. $K\subset \mathbb {R} ^{d}$ :

Максимальное определение : определение, описанное во введении к этой статье. Он основан на максимумах набора точек .
Классическое определение : ортогональная выпуклая оболочка. $K$ является пересечением всех ортогонально надмножеств выпуклых $K$ ; Оттманн, Сойсалон-Сойнинен и Вуд (1984) .
Связное определение : ортогональная выпуклая оболочка $K$ — наименьшее связное ортогонально выпуклое надмножество $K$ ; Николл и др. (1983) .
Функциональное определение : ортогональная выпуклая оболочка $K$ является пересечением нулевых множеств всех неотрицательных ортогонально выпуклых функций, которые $0$ на $K$ ; Матушек и Плегач (1998) .

На рисунках справа верхний рисунок показывает набор из шести точек на плоскости. Классическая ортогональная выпуклая оболочка множества точек представляет собой само множество точек. Сверху вниз на рисунках со второго по четвертый показаны соответственно максимальная, связная и функциональная ортогональная выпуклая оболочки множества точек. Как видно, ортогональная выпуклая оболочка представляет собой многоугольник с некоторыми вырожденными «ребрами», а именно, ортогонально-выпуклыми чередующимися цепочками ломаных с внутренним углом $90^{\circ }$ соединяющие крайние вершины.

Классическая ортогональная выпуклая оболочка

Классическую ортогональную выпуклую оболочку можно эквивалентным образом определить как наименьшее ортогонально выпуклое надмножество множества. $K\subset \mathbb {R} ^{2}$ , по аналогии со следующим определением выпуклой оболочки: выпуклая оболочка $K$ является наименьшим выпуклым надмножеством $K$ . Классическая ортогональная выпуклая оболочка может быть несвязной. Если набор точек не имеет пары точек на прямой, параллельной одному из стандартных базисных векторов, классическая ортогональная выпуклая оболочка такого набора точек равна самому набору точек.

Хорошо известное свойство выпуклых оболочек выводится из теоремы Каратеодори : точка $x\in \mathbb {R} ^{d}$ находится внутри выпуклой оболочки множества точек $K\subset \mathbb {R} ^{d}$ тогда и только тогда, когда оно уже находится в выпуклой оболочке $d+1$ или меньше баллов $K$ . Это свойство справедливо и для классических ортогональных выпуклых оболочек.

Связная ортогональная выпуклая оболочка

По определению связная ортогональная выпуклая оболочка всегда связна. Однако оно не уникально. Рассмотрим, например, пару точек плоскости, не лежащих на горизонтальной или вертикальной линии. Связная ортогональная выпуклая оболочка таких точек представляет собой ортогонально-выпуклую цепочку знакопеременных ломаных с внутренним углом $90^{\circ }$ соединяя точки. Любая такая ломаная цепочка имеет одинаковую длину, поэтому для множества точек существует бесконечно много связных ортогональных выпуклых оболочек.

Для множеств точек на плоскости связная ортогональная выпуклая оболочка легко может быть получена из максимальной ортогональной выпуклой оболочки. Если максимальная ортогональная выпуклая оболочка множества точек $K\subset \mathbb {R} ^{2}$ связна, то она равна связной ортогональной выпуклой оболочке $K$ . Если это не так, то существует бесконечно много связных ортогональных выпуклых оболочек для $K$ , и каждый из них может быть получен объединением компонент связности максимальной ортогональной выпуклой оболочки $K$ с ортогонально-выпуклыми чередующимися цепочками ломаных с внутренним углом $90^{\circ }$ .

Функциональная ортогональная выпуклая оболочка

Функциональная ортогональная выпуклая оболочка определяется не свойствами множеств, а свойствами функций о множествах. А именно, оно ограничивает понятие выпуклой функции следующим образом. Функция $f:\mathbb {R} ^{d}\rightarrow \mathbb {R}$ называется ортогонально выпуклой, если ее ограничение на каждую прямую, параллельную ненулевому стандартному базисному вектору, является выпуклой функцией.

Алгоритмы

Несколько авторов изучали алгоритмы построения ортогональных выпуклых оболочек: Montuno & Fournier (1982) ; Николл и др. (1983) ; Оттманн, Сойсалон-Сойнинен и Вуд (1984) ; Карлссон и Овермарс (1988) . По результатам этих авторов ортогональная выпуклая оболочка из $n$ точек на плоскости может быть построена за время $O (n log n)$ или, возможно, быстрее, используя структуры данных целочисленного поиска для точек с целочисленными координатами.

Связанные понятия

Ортогональную выпуклость естественно обобщить до выпуклости с ограниченной ориентацией , в которой множество $K$ определяется как выпуклое, если все линии, имеющие один из конечного набора наклонов, должны пересекать $K$ в связных подмножествах; см., например, Роулинз (1987) , Роулинз и Вуд ( 1987 , 1988 ) или Финк и Вуд ( 1996 , 1998 ).

Кроме того, узкая оболочка конечного метрического пространства тесно связана с ортогональной выпуклой оболочкой. Если конечное множество точек на плоскости имеет связную ортогональную выпуклую оболочку, эта оболочка представляет собой узкий диапазон манхэттенского расстояния на множестве точек. Однако ортогональные оболочки и узкие промежутки различаются для наборов точек с несвязными ортогональными оболочками или в многомерных L ^п пространства .

О'Рурк (1993) описывает несколько других результатов об ортогональной выпуклости и ортогональной видимости .

Ссылки

Бисвас, Ариндам; Бхоумик, Парта; Саркар, Мумита; Бхаттачарья, Бхаргаб Б. (2012), «Комбинаторный алгоритм линейного времени для поиска ортогональной оболочки объекта на цифровой плоскости» , Information Sciences , 216 : 176–195, doi : 10.1016/j.ins.2012.05.029 .
Финк, Юджин; Вуд, Дерик (1996), «Основы выпуклости с ограниченной ориентацией» (PDF) , Information Sciences , 92 (1–4): 175–196, doi : 10.1016/0020-0255(96)00056-4 , S2CID 17771224 .
Финк, Юджин; Вуд, Дерик (1998), «Обобщенные полупространства в выпуклости с ограниченной ориентацией» (PDF) , Journal of Geometry , 62 (1–2): 99–120, doi : 10.1007/BF01237603 , S2CID 14709697 .
Карлссон, Рольф Г.; Овермарс, Марк Х. (1988), «Алгоритмы развертки на сетке», BIT , 28 (2): 227–241, doi : 10.1007/BF01934088 , hdl : 1874/16270 , S2CID 32964283 .
Матушек Ю.; Плечач, П. (1998), «О функциональных отдельно выпуклых оболочках», Дискретная и вычислительная геометрия , 19 (1): 105–130, doi : 10.1007/PL00009331 .
Монтуно, ДЮ; Фурнье, А. (1982), Поиск $выпуклой оболочки x$ - $y$ набора $x$ - $y$ многоугольников , Технический отчет 148, Университет Торонто .
Николл, ТМ; Ли, DT ; Ляо, ЮЗ; Вонг, К.К. (1983), «О выпуклой оболочке XY набора многоугольников XY», BIT , 23 (4): 456–471, doi : 10.1007/BF01933620 , S2CID 10492640 .
О'Рурк, Джозеф (1993), Вычислительная геометрия на C , Cambridge University Press, стр. 107–109 .
Оттманн, Т.; Сойсалон-Сойнинен, Э.; Вуд, Дерик (1984), «Об определении и вычислении прямолинейных выпуклых оболочек», Information Sciences , 33 (3): 157–171, doi : 10.1016/0020-0255(84)90025-2 .
Роулинз, GJE (1987), Исследования в области геометрии ограниченной ориентации , доктор философии. диссертация и техн. Представитель CS-87-57, Университет Ватерлоо .
Роулинз, GJE; Вуд, Дерик (1987), «Оптимальное вычисление конечно ориентированных выпуклых оболочек», Information and Computation , 72 (2): 150–166, doi : 10.1016/0890-5401(87)90045-9 .
Роулинз, GJE; Вуд, Дерик (1988), «Орто-выпуклость и ее обобщения», в Туссен, Годфрид Т. (ред.), Вычислительная морфология , Elsevier, стр. 137–152 .