Относительно выпуклая оболочка - Relative convex hull

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

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

Определение

Позволять ${ displaystyle P}$ - простой многоугольник или спрямляемая простая замкнутая кривая, и пусть ${ displaystyle X}$ быть любым множеством, заключенным в ${ displaystyle P}$.A геодезический между двумя точками в ${ displaystyle P}$ это кратчайший путь, соединяющий эти две точки, который полностью находится внутри ${ displaystyle P}$Подмножество ${ displaystyle K}$ точек внутри ${ displaystyle P}$ называется относительно выпуклым, геодезически выпуклым или ${ displaystyle P}$-выпуклый, если для каждых двух точек ${ displaystyle K}$, геодезическая между ними в ${ displaystyle P}$ остается в пределах ${ displaystyle K}$. Тогда относительная выпуклая оболочка ${ displaystyle X}$ можно определить как пересечение всех относительно выпуклых множеств, содержащих ${ displaystyle X}$.^[1]

Эквивалентно, относительная выпуклая оболочка - это минимальный периметр слабо простой многоугольник в ${ displaystyle P}$ что включает ${ displaystyle X}$. Это была оригинальная формулировка относительных выпуклых оболочек. Склански, Чазин и Хансен (1972).^[2] Однако это определение усложняется необходимостью использовать слабо простые многоугольники (интуитивно, многоугольники, в которых граница многоугольника может касаться или перекрываться, но не пересекаться) вместо простые многоугольники когда ${ displaystyle X}$ отключен, и не все его компоненты видны друг другу.

Особые случаи

Конечные наборы точек

Туссен (1986), который предоставил эффективный алгоритм построения относительной выпуклой оболочки для конечных множеств точек внутри простой многоугольник.^[3] С последующим улучшением временных рамок для двух подпрограмм поиск кратчайших путей между точками запроса в многоугольнике,^[4] и триангуляция многоугольника,^[5] этот алгоритм требует времени ${ Displaystyle О (п + п журнал (п + п))}$ на входе с ${ displaystyle n}$ точки в многоугольнике с ${ displaystyle p}$ вершины.^[4] Его также можно поддерживать динамично в сублинейном времени на обновление.^[6]

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

Простые многоугольники

Для относительной выпуклой оболочки простых многоугольников можно использовать альтернативное, но эквивалентное определение выпуклости. Простой многоугольник ${ displaystyle P}$ внутри другого простого многоугольника ${ displaystyle Q}$ относительно выпуклый или ${ displaystyle Q}$-выпуклый, если каждый сегмент линии содержится в ${ displaystyle Q}$ который соединяет две точки ${ displaystyle P}$ лежит в пределах ${ displaystyle P}$. Относительно выпуклая оболочка простого многоугольника ${ displaystyle P}$ в ${ displaystyle Q}$ можно определить как пересечение всех ${ displaystyle Q}$-выпуклые многоугольники, содержащие ${ displaystyle P}$, как самый маленький ${ displaystyle Q}$-выпуклый многоугольник, содержащий ${ displaystyle P}$, или как простой многоугольник с минимальным периметром, содержащий ${ displaystyle P}$ и содержится ${ displaystyle Q}$.^[1]

Клетт (2010) обобщает линейное время алгоритмы для выпуклая оболочка простого многоугольника относительно выпуклой оболочки одного простого многоугольника внутри другого. Однако полученный обобщенный алгоритм не является линейным по времени: его временная сложность зависит от глубины вложенности определенных объектов одного многоугольника в другой. В этом случае относительная выпуклая оболочка сама по себе представляет собой простой многоугольник.^[1] Альтернативные алгоритмы линейного времени на основе планирование пути известны.^[7]

Аналогичное определение можно дать и для относительной выпуклой оболочки двух непересекающихся простых многоугольников. Этот тип корпуса может использоваться в алгоритмах для проверки того, можно ли разделить два многоугольника на непересекающиеся полуплоскости непрерывным линейным движением,^[8] и в структурах данных для обнаружение столкновения движущихся полигонов.^[9]

Высшие измерения

Определение относительной выпуклой оболочки на основе минимального ограждения не распространяется на более высокие размеры, потому что (даже без окружения внешней формой) ограждение с минимальной площадью поверхности невыпуклого набора обычно не является выпуклым.^[7] Однако для относительной выпуклой оболочки связного множества внутри другого набора можно использовать определение, аналогичное определению простых многоугольников. В этом случае относительно выпуклый набор снова может быть определен как подмножество данного внешнего набора, которое содержит все линейные сегменты внешнего набора между парами его точек. Относительно выпуклая оболочка может быть определена как пересечение всех относительно выпуклых множеств, содержащих внутреннее множество.^[10]

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