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

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

Определение

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

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

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

Конечные множества точек

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

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

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

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

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

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

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

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

Ссылки

^ Перейти обратно: ^а ^б ^с Клетте, Гизела (ноябрь 2010 г.), «Рекурсивный алгоритм расчета относительной выпуклой оболочки», 25-я Международная конференция по вычислениям изображений и изображений, Новая Зеландия , IEEE, стр. 1–7, doi : 10.1109/ivcnz.2010.6148857 , ISBN 978-1-4244-9631-0 , S2CID 17854252
^ Склански, Джек; Чазин, Роберт Л.; Хансен, Брюс Дж. (1972), «Многоугольники с минимальным периметром оцифрованных силуэтов», IEEE Transactions on Computers , C-21 (3): 260–268, doi : 10.1109/tc.1972.5008948 , S2CID 6818423
^ Туссен, Годфрид (1986), «Оптимальный алгоритм для вычисления относительной выпуклой оболочки набора точек многоугольника», Труды EURASIP, Обработка сигналов III: Теории и приложения, Часть 2 , Северная Голландия, стр. 853– 856
^ Перейти обратно: ^а ^б Гибас, Леонидас Дж .; Хершбергер, Джон (1989), «Запросы оптимального кратчайшего пути в простом многоугольнике», Journal of Computer and System Sciences , 39 (2): 126–152, doi : 10.1016/0022-0000(89)90041-X , MR 1024124
^ Шазель, Бернар (1991), «Триангуляция простого многоугольника за линейное время», Discrete & Computational Geometry , 6 (3): 485–524, doi : 10.1007/BF02574703
^ О, Ынджин; Ан, Хи-Кап (2017), «Динамические геодезические выпуклые оболочки в динамических простых многоугольниках», 33-й Международный симпозиум по вычислительной геометрии (SoCG 2017) , LIPIcs, vol. 77, Schloss Dagstuhl, стр. 51:1–51:15, doi : 10.4230/LIPIcs.SoCG.2017.51 , MR 3685723
^ Перейти обратно: ^а ^б Уильямс, Джейсон; Россиньяк, Ярек (2005), «Затягивание: морфологическое упрощение, ограничивающее кривизну», в Коббелте, Лейф; Шапиро, Вадим (ред.), Труды десятого симпозиума ACM по твердотельному и физическому моделированию, 2005 г., Кембридж, Массачусетс, США, 13–15 июня 2005 г. , ACM, стр. 107–112, doi : 10.1145/1060244.1060257 , hdl : 1853/3736 , S2CID 15514388
^ Туссен, Годфрид (1989), «О разделении двух простых многоугольников одним сдвигом», Discrete & Computational Geometry , 4 (3): 265–278, doi : 10.1007/BF02187729 , MR 0988749
^ Баш, Жюльен; Эриксон, Джефф; Гибас, Леонидас Дж .; Хершбергер, Джон ; Чжан, Ли (2004), «Кинетическое обнаружение столкновений между двумя простыми многоугольниками», Computational Geometry , 27 (3): 211–235, doi : 10.1016/j.comgeo.2003.11.001 , MR 2039172 , S2CID 300999
^ Слобода, Фридрих; Зако, Бедрич (2001), «Об аппроксимации жордановых поверхностей в 3d», Бертран, Г.; Имия, А.; Клетт, Р. (ред.), Цифровая и графическая геометрия: продвинутые лекции , Конспекты лекций по информатике, том. 2243, Springer, стр. 365–386, номер документа : 10.1007/3-540-45576-0_22 , ISBN. 978-3-540-43079-7

[klette-1] Перейти обратно: ^а ^б ^с Клетте, Гизела (ноябрь 2010 г.), «Рекурсивный алгоритм расчета относительной выпуклой оболочки», 25-я Международная конференция по вычислениям изображений и изображений, Новая Зеландия , IEEE, стр. 1–7, doi : 10.1109/ivcnz.2010.6148857 , ISBN 978-1-4244-9631-0 , S2CID 17854252

[sch-2] Склански, Джек; Чазин, Роберт Л.; Хансен, Брюс Дж. (1972), «Многоугольники с минимальным периметром оцифрованных силуэтов», IEEE Transactions on Computers , C-21 (3): 260–268, doi : 10.1109/tc.1972.5008948 , S2CID 6818423

[optimal-3] Туссен, Годфрид (1986), «Оптимальный алгоритм для вычисления относительной выпуклой оболочки набора точек многоугольника», Труды EURASIP, Обработка сигналов III: Теории и приложения, Часть 2 , Северная Голландия, стр. 853– 856

[pathquery-4] Перейти обратно: ^а ^б Гибас, Леонидас Дж .; Хершбергер, Джон (1989), «Запросы оптимального кратчайшего пути в простом многоугольнике», Journal of Computer and System Sciences , 39 (2): 126–152, doi : 10.1016/0022-0000(89)90041-X , MR 1024124

[triangulate-5] Шазель, Бернар (1991), «Триангуляция простого многоугольника за линейное время», Discrete & Computational Geometry , 6 (3): 485–524, doi : 10.1007/BF02574703

[dynamic-6] О, Ынджин; Ан, Хи-Кап (2017), «Динамические геодезические выпуклые оболочки в динамических простых многоугольниках», 33-й Международный симпозиум по вычислительной геометрии (SoCG 2017) , LIPIcs, vol. 77, Schloss Dagstuhl, стр. 51:1–51:15, doi : 10.4230/LIPIcs.SoCG.2017.51 , MR 3685723

[tightening-7] Перейти обратно: ^а ^б Уильямс, Джейсон; Россиньяк, Ярек (2005), «Затягивание: морфологическое упрощение, ограничивающее кривизну», в Коббелте, Лейф; Шапиро, Вадим (ред.), Труды десятого симпозиума ACM по твердотельному и физическому моделированию, 2005 г., Кембридж, Массачусетс, США, 13–15 июня 2005 г. , ACM, стр. 107–112, doi : 10.1145/1060244.1060257 , hdl : 1853/3736 , S2CID 15514388

[separate-8] Туссен, Годфрид (1989), «О разделении двух простых многоугольников одним сдвигом», Discrete & Computational Geometry , 4 (3): 265–278, doi : 10.1007/BF02187729 , MR 0988749

[kinetic-9] Баш, Жюльен; Эриксон, Джефф; Гибас, Леонидас Дж .; Хершбергер, Джон ; Чжан, Ли (2004), «Кинетическое обнаружение столкновений между двумя простыми многоугольниками», Computational Geometry , 27 (3): 211–235, doi : 10.1016/j.comgeo.2003.11.001 , MR 2039172 , S2CID 300999

[sz-10] Слобода, Фридрих; Зако, Бедрич (2001), «Об аппроксимации жордановых поверхностей в 3d», Бертран, Г.; Имия, А.; Клетт, Р. (ред.), Цифровая и графическая геометрия: продвинутые лекции , Конспекты лекций по информатике, том. 2243, Springer, стр. 365–386, номер документа : 10.1007/3-540-45576-0_22 , ISBN. 978-3-540-43079-7

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]