В геометрії, множина буде ортогонально опуклою, якщо для будь-якої прямої , паралельної одному зі стандартних базисних векторів Rn, перетин з буде або порожнім або точкою або відрізком. Термін «ортогональний» стосується відповідного декартового базису і координат в евклідовому просторі, де різні базисні вектори перпендикулярні, а також до відповідних прямих. На відміну від звичайних опуклих множин, ортогонально опукла оболонка не обов'язково буде зв'язною множиною.
Ортогональна опукла оболонка множини є перетином всіх зв'язних ортогонально опуклих множин, що містять .
Ці визначення зроблені за аналогією з класичною теорією опуклості, в якій множина є опуклою, якщо для будь-якої прямої , перетин з буде порожньою множиною, точкою, або сегментом (інтервалом). Ортогональна опуклість обмежує множину прямих, для яких ця властивість виконується. Таким чином, кожна опукла множина буде ортогонально опуклою але не навпаки. З тієї ж причини, ортогональна опукла оболонка сама є підмножиною опуклої оболонки того ж набору точок. Точка належить ортогональній опуклій оболонці тоді і тільки тоді, коли кожен із закритих, вирівняних по осях ортів, що містить як вершину, має непорожній перетин з .
Ортогональна опукла оболонка також знана як прямолінійна опукла оболонка, або, двовимірна - опукла оболонка.
Приклад На малюнку показано набір з 16 точок на площині та їх ортогональна опукла оболонка. Як можна бачити на малюнку, ортогональна опукла оболонка являє собою багатокутник, який містить вироджені ребра, що з'єднують крайні вершини в кожному координатному напрямку. Для дискретної множини точок, такій як ця, усі ортогональні опуклі краї оболонки горизонтальні або вертикальні. У наведеному прикладі ортогональна опукла оболонка зв'язна.
Алгоритми Наступні автори досліджували алгоритми побудови ортогональних опуклих оболонок: Montuno & Fournier (1982.); Nicholl et al. (1983.); Ottman, Soisalon-Soisinen & Wood (1984.); Karlsson & Overmars (1988.). У підсумку можна стверджувати, що ортогональна опукла оболонка точок на площині може бути побудовано за час , або, можливо, і швидше, якщо використовувати цілочисельні пошукові структури даних для точок з цілими координатами.
Пов'язані поняття Природно узагальнити ортогональну опуклість, як обмежено орієнтовану опуклість, в якій множина є опуклою, якщо кожна пряма, яка паралельна одному з кінцевого набору напрямків, перетинає по зв'язній підмножині; див., наприклад Rawlins(1987. ), Rawlins та Wood (1987., 1988), або Fink та Wood (1996., 1998.).
Крім того, метрична обгортка метричного простору тісно пов'язана з ортогональною опуклою оболонкою. Якщо скінченна множина точок на площині має зв'язну ортогонально опуклу оболонку, тоді оболонка буде метричною обгорткою для манхеттенської метрики на множині точок. Проте, ортогональна оболонка і метрична обгортка відрізняються у випадку множин точок з незв'язною ортогональною оболонкою, або в багатовимірних L р просторах.
O'Rourke (1993.) описує дещо інші результати по ортогональній опуклості і ортогональній видимості.
Посилання