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

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

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

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

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

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

Пример

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

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

Набор из шести точек на плоскости. В Классическая ортовыпуклая оболочка это точка, установленная сама собой.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Алгоритмы

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

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

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

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

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