Kadłub wypukły ortogonalny

Ortogonalna wypukła powłoka zbioru punktów

W geometrii zbiór $K \subset R d$ jest $ortogonalnie$ wypukły , jeśli dla każdej prostej $L$ , która jest równoległa do jednego ze standardowych wektorów bazowych, przecięcie K z $L$ jest puste, jest punktem lub pojedynczym odcinkiem . Termin „ortogonalny” odnosi się do odpowiedniej kartezjańskiej i współrzędnych w przestrzeni euklidesowej , gdzie różne wektory bazowe są prostopadłe , jak również odpowiednie linie. W przeciwieństwie do zwykłych zbiorów wypukłych , zbiór ortogonalnie wypukły niekoniecznie jest spójny .

Ortogonalna wypukła otoczka zbioru $K \subset R d$ jest przecięciem wszystkich połączonych ortogonalnie wypukłych nadzbiorów zbioru $K$ .

Definicje te są tworzone przez analogię do klasycznej teorii wypukłości, w której $K$ jest wypukłe , jeśli dla każdej prostej $L$ przecięcie $K$ z $L$ jest puste, jest punktem lub pojedynczym odcinkiem. Wypukłość ortogonalna ogranicza linie, dla których ta właściwość musi być zachowana, więc każdy zbiór wypukły jest wypukły ortogonalnie, ale nie odwrotnie. Z tego samego powodu sam ortogonalny wypukły kadłub jest podzbiorem wypukłego kadłuba tego samego zbioru punktów. Punkt $p$ należy do ortogonalnej wypukłej otoczki $K$ orthantów wyrównanych do osi zamkniętych, których wierzchołkiem jest $p$ , ma niepuste przecięcie z $K$ .

Ortogonalna wypukła powłoka jest również znana jako prostoliniowa wypukła powłoka lub, w dwóch wymiarach , wypukła powłoka $x$ - $y$ .

Przykład

Rysunek przedstawia zbiór 16 punktów na płaszczyźnie oraz ortogonalną wypukłą otoczkę tych punktów. Jak widać na rysunku, ortogonalna wypukła otoczka jest wielokątem z kilkoma zdegenerowanymi krawędziami łączącymi skrajne wierzchołki w każdym kierunku współrzędnych. W przypadku dyskretnego zbioru punktów, takiego jak ten, wszystkie prostopadłe wypukłe krawędzie kadłuba są poziome lub pionowe. W tym przykładzie ortogonalna wypukła otoczka jest połączona.

Alternatywne definicje

Zbiór sześciu punktów na płaszczyźnie. Klasyczny orto-wypukły kadłub jest sam w sobie punktem.

Maksymalny orto-wypukły kadłub zbioru punktów górnej figury. Jest tworzony przez zbiór punktów i kolorowy obszar.

Połączony orto-wypukły kadłub zbioru punktów górnej figury. Jest tworzony przez zbiór punktów, kolorowy obszar i dwa orto-wypukłe łańcuchy wielokątne.

Funkcjonalny orto-wypukły kadłub zbioru punktów górnej figury. Składa się z zestawu punktów, kolorowego obszaru i czterech segmentów linii.

W przeciwieństwie do klasycznej wypukłości, w której istnieje kilka równoważnych definicji otoczki wypukłej, definicje ortogonalnej otoczki wypukłej dokonane przez analogię do definicji wypukłej otoczki dają różne obiekty geometryczne. Do tej pory badacze zbadali następujące cztery definicje ortogonalnego wypukłego kadłuba zbioru: ${\ Displaystyle K \ podzbiór \ mathbb {R} ^ {d}}$ :

Definicja maksymalna : Definicja opisana we wstępie do tego artykułu. Opiera się na maksimach zbioru punktów .
$K$ definicja : Ortogonalny wypukły kadłub jest przecięciem wszystkich ortogonalnie wypukłych nadzbiorów K. {\ $}$ ; Ottmann, Soisalon-Soininen & Wood (1984) .
Połączona definicja : ortogonalny wypukły kadłub jest najmniejszym połączonym ortogonalnie wypukłym nadzbiorem $K}$ $displaystyle$ ; Nicholl i in. (1983) .
Definicja funkcjonalna : ortogonalna wypukła powłoka jest przecięciem zerowych zbiorów wszystkich nieujemnych funkcji wypukłych ortogonalnie, które są $na$ K $K}$ $displaystyle$ ; Matoušek i Plecháč (1998) .

Na rysunkach po prawej stronie górny rysunek przedstawia zestaw sześciu punktów na płaszczyźnie. Klasyczny ortogonalny wypukły kadłub zbioru punktów jest samym zbiorem punktów. Od góry do dołu, figury od drugiej do czwartej przedstawiają odpowiednio maksymalną, połączoną i funkcjonalną ortogonalną wypukłą powłokę zbioru punktów. Jak widać, ortogonalny wypukły kadłub jest wielokątem $kącie wewnętrznym$ pewnymi zdegenerowanymi „krawędziami”, a mianowicie ortogonalnie wypukłymi naprzemiennymi wielokątów o łączącym skrajne wierzchołki.

Klasyczny ortogonalny wypukły kadłub

Klasyczny ortogonalny wypukły kadłub można równoważnie zdefiniować jako najmniejszy ortogonalnie wypukły nadzbiór zbioru , analogicznie do następującej definicji wypukłego kadłuba: ${\ Displaystyle K \ podzbiór \ mathbb {R} ^ {2}}}$ wypukła powłoka jest najmniejszym wypukłym nadzbiorem $displaystyle$ $K}$ . Klasyczna ortogonalna powłoka wypukła może być rozłączona. Jeśli zbiór punktów nie ma pary punktów na prostej równoległej do jednego ze standardowych wektorów bazowych, to klasyczny ortogonalny wypukły kadłub takiego zbioru punktów jest równy samemu zbiorowi punktów.

Dobrze znana właściwość powłok wypukłych wywodzi się z $twierdzenia$ : Punkt znajduje we wnętrzu wypukłej powłoki ${\ Displaystyle K \ podzbiór \ mathbb {R} ^ {d}}$ wtedy i tylko wtedy, gdy znajduje się już w wypukłej otoczce ${\ displaystyle d + 1}$ lub mniej punktów ${\ displaystyle K}$ . Właściwość ta jest również ważna dla klasycznych ortogonalnych wypukłych kadłubów.

Połączony ortogonalny wypukły kadłub

Z definicji spójny ortogonalny wypukły kadłub jest zawsze spójny. Jednak nie jest wyjątkowy. Rozważmy na przykład parę punktów na płaszczyźnie, które nie leżą na linii poziomej ani pionowej. Połączona ortogonalna wypukła otoczka takich punktów jest ortogonalnie wypukłym naprzemiennym łańcuchem wielokątnym z kątem wewnętrznym łączącym punkty ${\ displaystyle 90 ^ {\ circ}} .$ Każdy taki wielokątny łańcuch ma tę samą długość, więc istnieje nieskończenie wiele połączonych ortogonalnych wypukłych kadłubów dla zbioru punktów.

W przypadku zbiorów punktów w płaszczyźnie połączoną ortogonalną otoczkę wypukłą można łatwo uzyskać z maksymalnej ortogonalnej wypukłej otoczki. Jeśli maksymalny ortogonalny wypukły kadłub zbioru punktów jest połączony, to jest równy połączonemu ortogonalnemu wypukłemu kadłubowi $\ podzbiór \ mathbb {R} ^ {2}$ $}$ . Jeśli tak nie jest, to istnieje nieskończenie wiele połączonych ortogonalnych wypukłych kadłubów dla i każdy z nich można uzyskać, łącząc połączone składowe maksymalnego ortogonalnego wypukłego kadłuba K {\ $K}$ ${\ displaystyle K}$ z ortogonalnie wypukłymi naprzemiennymi łańcuchami wielokątnymi o kącie wewnętrznym ${\ Displaystyle 90 ^ {\ circ}}$ .

Funkcjonalny ortogonalny wypukły kadłub

Funkcjonalna ortogonalna otoczka wypukła nie jest definiowana za pomocą właściwości zbiorów, ale właściwości funkcji o zbiorach. Mianowicie ogranicza pojęcie funkcji wypukłej w następujący sposób. Funkcja ${\ Displaystyle f: \ mathbb {R} ^ {d} \ rightarrow \ mathbb {R}}$ nazywana jest ortogonalnie wypukłą, jeśli jej ograniczenie do każdej prostej równoległej do niezerowej podstawy standardowej fa : R re → R {\ Displaystyle f: \ mathbb {R} ^ {d} \ rightarrow \ mathbb {R}} wektory jest funkcją wypukłą.

Algorytmy

Kilku autorów badało algorytmy konstruowania ortogonalnych wypukłych kadłubów: Montuno i Fournier (1982) ; Nicholl i in. (1983) ; Ottmann, Soisalon-Soininen & Wood (1984) ; Karlsson i Overmars (1988) . Na podstawie wyników tych autorów ortogonalna wypukła powłoka $n$ punktów na płaszczyźnie może być skonstruowana w czasie $O (n log n)$ lub być może szybciej przy użyciu struktur danych przeszukujących liczby całkowite dla punktów o współrzędnych całkowitych .

Pojęcia pokrewne

Naturalne jest uogólnienie wypukłości ortogonalnej na wypukłość o ograniczonej orientacji , w której zbiór $K$ jest zdefiniowany jako wypukły, jeśli wszystkie linie mające jedno ze skończonego zbioru nachyleń muszą przecinać $K$ w połączonych podzbiorach; patrz np. Rawlins (1987) , Rawlins i Wood ( 1987 , 1988 ) lub Fink i Wood ( 1996 , 1998 ).

Ponadto ciasna rozpiętość skończonej przestrzeni metrycznej jest ściśle związana z ortogonalnym wypukłym kadłubem. Jeśli skończony punkt ustawiony na płaszczyźnie ma połączony ortogonalny wypukły kadłub, ten kadłub jest wąską rozpiętością dla odległości Manhattanu na zbiorze punktów. Jednak kadłuby ortogonalne i ciasne rozpiętości różnią się dla zbiorów punktowych z rozłączonymi kadłubami ortogonalnymi lub w przestrzeniach L ^{p o} wyższych wymiarach .

O'Rourke (1993) opisuje kilka innych wyników dotyczących wypukłości ortogonalnej i widoczności ortogonalnej .

Biswas, Arindam; Bhowmick, Partha; Sarkar, Moumita; Bhattacharya, Bhargab B. (2012), „Algorytm kombinatoryczny w czasie liniowym do znajdowania ortogonalnego kadłuba obiektu na płaszczyźnie cyfrowej” , Information Sciences , 216 : 176–195, doi : 10.1016/j.ins.2012.05.029 .
Fink, Eugeniusz; Wood, Derick (1996), „Podstawy wypukłości o ograniczonej orientacji” (PDF) , Information Sciences , 92 (1–4): 175–196, doi : 10.1016/0020-0255 (96) 00056-4 .
Fink, Eugeniusz; Wood, Derick (1998), „Uogólnione półprzestrzenie w wypukłościach o ograniczonej orientacji” (PDF) , Journal of Geometry , 62 (1–2): 99–120, doi : 10.1007 / BF01237603 , S2CID 14709697 .
Karlsson, Rolf G.; Overmars, Mark H. (1988), „Algorytmy linii skanowania na siatce”, BIT , 28 (2): 227–241, doi : 10.1007/BF01934088 , hdl : 1874/16270 , S2CID 32964283 .
Matoušek, J.; Plecháč, P. (1998), „O funkcjonalnych oddzielnie wypukłych kadłubach”, Discrete & Computational Geometry , 19 (1): 105–130, doi : 10.1007 / PL00009331 .
Montuno, DY; Fournier, A. (1982), Finding the $x$ - $y$ convex hull of the set of $x$ - $y$ polygons , Technical Report 148, University of Toronto .
Nicholl, TM; Lee, DT ; Liao, YZ; Wong, CK (1983), „Na wypukłym kadłubie XY zestawu wielokątów XY”, BIT , 23 (4): 456–471, doi : 10.1007 / BF01933620 , S2CID 10492640 .
O'Rourke, Joseph (1993), Geometria obliczeniowa w C , Cambridge University Press, s. 107–109 .
Ottmann, T.; Soisalon-Soininen, E.; Wood, Derick (1984), „O definicji i obliczaniu prostoliniowych wypukłych kadłubów”, Information Sciences , 33 (3): 157–171, doi : 10.1016/0020-0255 (84) 90025-2 .
Rawlins, GJE (1987), Explorations in Restricted-Orientation Geometry , Ph.D. praca dyplomowa i technika. Przedstawiciel CS-87-57, Uniwersytet Waterloo .
Rawlins, GJE; Wood, Derick (1987), „Optymalne obliczenia skończenie zorientowanych wypukłych kadłubów”, Information and Computation , 72 (2): 150–166, doi : 10.1016/0890-5401 (87) 90045-9 .
Rawlins, GJE; Wood, Derick (1988), „Ortho-wypukłość i jej uogólnienia”, w Toussaint, Godfried T. (red.), Computational Morphology , Elsevier, s. 137–152 .