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

Минимальное надмножество, пересекающее каждую параллельную оси линию в интервале

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

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

Ортогональная выпуклая оболочка множества K ⊂ R ^d — это пересечение всех связных ортогонально выпуклых надмножеств K .

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

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

Пример

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

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

Множество из шести точек на плоскости. Классическая орто-выпуклая оболочка — это само множество точек.

Максимальная орто-выпуклая оболочка множества точек верхней фигуры. Образована множеством точек и закрашенной областью.

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

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

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

1. Максимальное определение : Определение, описанное во введении к этой статье. Оно основано на Максимуме множества точек .
2. Классическое определение : ортогональная выпуклая оболочка — это пересечение всех ортогонально выпуклых надмножеств ; Оттманн, Сойсалон-Сойнинен и Вуд (1984). ${\displaystyle K}$ ${\displaystyle K}$
3. Связное определение : ортогональная выпуклая оболочка — это наименьшее связное ортогонально выпуклое надмножество ; Николл и др. (1983). ${\displaystyle K}$ ${\displaystyle K}$
4. Функциональное определение : ортогональная выпуклая оболочка — это пересечение нулевых множеств всех неотрицательных ортогонально выпуклых функций, лежащих на ; Matoušek & Plecháč (1998). ${\displaystyle K}$ ${\displaystyle 0}$ ${\displaystyle K}$

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

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

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

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

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

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

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

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

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

Алгоритмы

Несколько авторов изучали алгоритмы построения ортогональных выпуклых оболочек: Montuno & Fournier (1982); Nicholl et al. (1983); Ottmann, Soisalon-Soininen & Wood (1984); Karlsson & Overmars (1988). По результатам этих авторов ортогональная выпуклая оболочка n точек на плоскости может быть построена за время O ( n log  n ) или, возможно, быстрее, используя целочисленные структуры данных поиска для точек с целочисленными координатами.

Связанные концепции

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

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

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

Ссылки

• Biswas, Arindam; Bhowmick, Partha; Sarkar, Moumita; Bhattacharya, Bhargab B. (2012), «Линейный комбинаторный алгоритм для поиска ортогональной оболочки объекта на цифровой плоскости», Information Sciences , 216 : 176–195, doi :10.1016/j.ins.2012.05.029.
• Финк, Юджин; Вуд, Дерик (1996), «Основы выпуклости ограниченной ориентации» (PDF) , Информационные науки , 92 (1–4): 175–196, doi :10.1016/0020-0255(96)00056-4, S2CID  17771224.
• Финк, Юджин; Вуд, Дерик (1998), «Обобщенные полупространства в выпуклости ограниченной ориентации» (PDF) , Журнал геометрии , 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, Университет Торонто.
• Николл, TM; Ли, DT ; Ляо, YZ; Вонг, CK (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), «Оптимальное вычисление конечно ориентированных выпуклых оболочек», Информация и вычисления , 72 (2): 150–166, doi : 10.1016/0890-5401(87)90045-9.
• Роулинс, GJE; Вуд, Дерик (1988), «Орто-выпуклость и ее обобщения», в Туссэн, Годфрид Т. (ред.), Вычислительная морфология , Elsevier, стр. 137–152.