Cyfroteka.pl

klikaj i czytaj online

Cyfro
Czytomierz
00062 008462 10460761 na godz. na dobę w sumie
Geometria obliczeniowa. Wprowadzenie - książka
Geometria obliczeniowa. Wprowadzenie - książka
Autor: , Liczba stron: 392
Wydawca: Helion Język publikacji: polski
ISBN: 83-7361-098-7 Data wydania:
Lektor:
Kategoria: ebooki >> komputery i informatyka >> programowanie >> inne - programowanie
Porównaj ceny (książka, ebook, audiobook).
W ostatniej dekadzie systematyczne badania algorytmów geometrycznych spowodowały utworzenie nowej dziedziny badawczej -- geometrii obliczeniowej. Jej osiągnięcia mają szerokie zastosowanie w przeżywającej ostatnio błyskawiczny rozwój trójwymiarowej grafice komputerowej, a także w automatyce, robotyce i w statystyce. Książka niniejsza to obszerny, systematyczny i jednolity wykład na ten temat. Stanowi ona klasyczną pozycję w tym zakresie informatyki.

Najważniejszym zadaniem geometrii obliczeniowej jest wskazanie pojęć, właściwości i technik, które będą pomocne przy tworzeniu sprawnych algorytmów rozwiązujących problemy z dziedziny geometrii.

Tematy poruszane w tej książce, to między innymi:

W książce metody geometrii obliczeniowej prezentowane są przez szczegółowe omówienie konkretnych przypadków. Początkowo książka ta miała być podręcznikiem dla studentów, ale w jej obecnym kształcie będzie przydatna także dla badaczy i dla osób zawodowo zajmujących się projektowaniem wspomaganym komputerowo, grafiką komputerową i robotyką.
Znajdź podobne książki Ostatnio czytane w tej kategorii

Darmowy fragment publikacji:

IDZ DO IDZ DO PRZYK£ADOWY ROZDZIA£ PRZYK£ADOWY ROZDZIA£ SPIS TREĎCI SPIS TREĎCI KATALOG KSI¥¯EK KATALOG KSI¥¯EK KATALOG ONLINE KATALOG ONLINE ZAMÓW DRUKOWANY KATALOG ZAMÓW DRUKOWANY KATALOG TWÓJ KOSZYK TWÓJ KOSZYK DODAJ DO KOSZYKA DODAJ DO KOSZYKA CENNIK I INFORMACJE CENNIK I INFORMACJE ZAMÓW INFORMACJE ZAMÓW INFORMACJE O NOWOĎCIACH O NOWOĎCIACH ZAMÓW CENNIK ZAMÓW CENNIK CZYTELNIA CZYTELNIA FRAGMENTY KSI¥¯EK ONLINE FRAGMENTY KSI¥¯EK ONLINE Wydawnictwo Helion ul. Chopina 6 44-100 Gliwice tel. (32)230-98-63 e-mail: helion@helion.pl Geometria obliczeniowa. Wprowadzenie Autorzy: Franco P. Preparata, Michael Ian Shamos T³umaczenie: Tomasz ¯mijewski ISBN: 83-7361-098-7 Tytu³ orygina³u: Computational Geometry. An Introduction Format: B5, stron: 386 W ostatniej dekadzie systematyczne badania algorytmów geometrycznych spowodowa³y utworzenie nowej dziedziny badawczej -- geometrii obliczeniowej. Jej osi¹gniêcia maj¹ szerokie zastosowanie w prze¿ywaj¹cej ostatnio b³yskawiczny rozwój trójwymiarowej grafice komputerowej, a tak¿e w automatyce, robotyce i w statystyce. Ksi¹¿ka niniejsza to obszerny, systematyczny i jednolity wyk³ad na ten temat. Stanowi ona klasyczn¹ pozycjê w tym zakresie informatyki. Najwa¿niejszym zadaniem geometrii obliczeniowej jest wskazanie pojêæ, w³aġciwoġci i technik, które bêd¹ pomocne przy tworzeniu sprawnych algorytmów rozwi¹zuj¹cych problemy z dziedziny geometrii. Tematy poruszane w tej ksi¹¿ce, to miêdzy innymi: • podstawy geometrii i historia geometrii obliczeniowej • wyszukiwanie geometryczne • uzyskiwanie informacji o obiektach • tworzenie otoczki wypuk³ej wraz z szeregiem problemów z tym zagadnieniem zwi¹zanych, • s¹siedztwo, przeciêcia oraz geometria prostok¹tów W ksi¹¿ce metody geometrii obliczeniowej prezentowane s¹ przez szczegó³owe omówienie konkretnych przypadków. Pocz¹tkowo ksi¹¿ka ta mia³a byæ podrêcznikiem dla studentów, ale w jej obecnym kszta³cie bêdzie przydatna tak¿e dla badaczy i dla osób zawodowo zajmuj¹cych siê projektowaniem wspomaganym komputerowo, grafik¹ komputerow¹ i robotyk¹. Spis treści Wstęp do wydania drugiego...................................................y............................9 Wstęp ...................................................y...................................................y..............11 1 Wprowadzenie ...................................................y.................................................13 1.1. Rys historyczny...................................................o...................................................o..... ...............13 1.1.1. Złożoność geometrii klasycznej ...................................................o.....................................14 1.1.2. Teoria zbiorów wypukłych, geometria metryczna i kombinatoryczna ............................16 1.1.3. Wcześniejsze prace ...................................................o...................................................o.....16 1.1.4. Ku geometrii obliczeniowej ...................................................o...........................................17 1.2. Wprowadzenie do algorytmów ...................................................o..............................................17 1.2.1. Algorytmy: zapis i określanie wydajności...................................................o.....................18 1.2.2. Nieco o technikach tworzenia algorytmów ...................................................o...................21 1.2.3. Struktury danych ...................................................o...................................................o........22 1.3. Podstawy geometrii.................................................o...................................................o................28 1.3.1. Definicje ogólne, przyjęte konwencje...................................................o.............................28 1.3.2. Niezmienniki grup przekształceń liniowych ...................................................o.................30 1.3.3. Dualność geometryczna. Biegunowość ...................................................o.........................35 ...........37 1.4. Modele obliczeniowe...................................................o...................................................o. 2 Przeszukiwanie geometryczne...................................................y.......................47 2.1. Wprowadzenie do przeszukiwania geometrycznego ...................................................o.............47 2.2. Problemy lokalizacji punktu ...................................................o...................................................51 2.2.1. Rozważania ogólne. Najprostsze przypadki ...................................................o.................51 2.2.2. Lokalizacja punktu w obszarze płaszczyzny...................................................o.................55 2.3. Problemy związane z przeszukiwaniem zakresu ...................................................o...................78 2.3.1. Rozważania ogólne...................................................o...................................................o. ....78 2.3.2. Metoda wielowymiarowego drzewa binarnego (k-D drzewa).........................................83 2.3.3. Metoda bezpośredniego dostępu i jej odmiany...................................................o.............87 2.3.4. Metoda drzew zakresu i jej odmiany...................................................o.............................91 6 SPIS TREŚCI 2.4. Szukanie iterowane i kaskadowanie ułamkowe ...................................................o.....................96 2.5. Uwagi i komentarze...................................................o...................................................o.. ...........99 ................ 101 2.6. Ćwiczenia...................................................o...................................................o........... 3 Otoczki wypukłe: algorytmy podstawowe...................................................y103 3.1. Informacje wstępne ...................................................o...................................................o............ 103 3.2. Sformułowanie problemu i ograniczenia dolne ...................................................o.................... 107 3.3. Algorytmy otoczki wypukłej na płaszczyźnie ...................................................o...................... 111 3.3.1. Pierwsze dokonania w dziedzinie algorytmów otoczki wypukłej ................................. 111 3.3.2. Skan Grahama...................................................o...................................................o...... ..... 114 3.3.3. Marsz Jarvisa ...................................................o...................................................o............ 117 3.3.4. Techniki QUICKHULL ...................................................o................................................ 119 3.3.5. Algorytmy typu „dziel i rządź”...................................................o................................... 121 3.3.6. Dynamiczne algorytmy otoczki wypukłej...................................................o................... 124 3.3.7. Uogólnienie: zachowanie otoczki wypukłej ...................................................o................ 130 3.4. Otoczki wypukłe w większej liczbie wymiarów niż dwa...................................................o..... 136 3.4.1. Metoda opakowywania prezentu...................................................o................................ 137 3.4.2. Metoda „pod-poza”...................................................o...................................................o.. 142 3.4.3. Trójwymiarowe otoczki wypukłe...................................................o................................ 145 ......... 150 ................ 152 3.5. Uwagi i komentarze...................................................o...................................................o.. 3.6. Ćwiczenia...................................................o...................................................o........... 4 Otoczki wypukłe: rozszerzenia i zastosowanie ...........................................155 4.1. Rozszerzenia i odmiany ...................................................o........................................................ 155 4.1.1. Analiza przypadku średniego ...................................................o..................................... 155 4.1.2. Algorytmy przybliżenia otoczki wypukłej ...................................................o.................. 159 4.1.3. Problem maksimów zbioru punktów...................................................o.......................... 162 4.1.4. Otoczka wypukła wielokąta prostego ...................................................o......................... 170 4.2. Zastosowania statystyczne...................................................o.................................................... 174 4.2.1. Solidne oszacowania...................................................o.................................................... 175 4.2.2. Regresja izotoniczna ...................................................o.................................................... 177 4.2.3. Klastrowanie (średnica zbioru punktów) ...................................................o.................... 179 ......... 185 ................ 186 4.3. Uwagi i komentarze...................................................o...................................................o.. 4.4. Ćwiczenia...................................................o...................................................o........... 5 Bliskość: algorytmy podstawowe...................................................y................187 5.1. Zbiór problemów ...................................................o...................................................o..... .......... 188 5.2. Prototyp obliczeniowy: niepowtarzalność elementu ...................................................o............ 193 5.3. Ograniczenia dolne..............................o...................................................o....................... ........... 194 5.4. Problem najbliższej pary: metoda „dziel i rządź”...................................................o................... 196 5.5. Rozwiązywanie lokalne problemów bliskości: diagram Voronoi............................................ 205 5.5.1. Właściwości Voronoi ...................................................o................................................... 206 5.5.2. Tworzenie diagramu Voronoi..................................................o....................................... 212 SPIS TREŚCI 7 5.6. Rozwiązywanie problemów sąsiedztwa diagramem Voronoi................................................. 219 5.7. Uwagi i komentarze...................................................o...................................................o.. ......... 222 ................ 223 5.8. Ćwiczenia...................................................o...................................................o........... 6 Bliskość: odmiany i uogólnienia...................................................y..................225 6.1. Euklidesowe drzewa minimalne...................................................o...........................................225 6.1.1. Problem komiwojażera w przestrzeni euklidesowej ...................................................o... 228 6.2. Triangulacje płaskie............................o...................................................o................................... 232 6.2.1. Triangulacja zachłanna...................................................o................................................. 233 6.2.2. Triangulacje ograniczone ...................................................o.............................................235 .. 238 6.3.1. Diagramy Voronoi wyższego rzędu (na płaszczyźnie) .................................................. 239 6.3.2. Wielowymiarowe diagramy Voronoi punktu najbliższego i punktu najdalszego......... 249 ........... 252 ......... 258 ................ 260 6.4. Przerwy i pokrycia...................................................o...................................................o.. 6.5. Uwagi i komentarze...................................................o...................................................o.. 6.6. Ćwiczenia...................................................o...................................................o........... 6.3. Uogólnienia diagramu Voronoi......................o...................................................o..................... 7 Przecięcia...................................................y...................................................y......263 7.1. Przykładowe zastosowania...................................................o................................................... 264 7.1.1. Problemy ukrytych linii i ukrytych powierzchni...................................................o......... 264 7.1.2. Rozpoznawanie wzorca...................................................o............................................... 265 7.1.3. Układ ścieżek i elementów ...................................................o.......................................... 266 7.1.4. Programowanie liniowe i wspólne przecięcie półprzestrzeni ........................................ 267 7.2. Zastosowania na płaszczyźnie ...................................................o.............................................. 268 7.2.1. Przecięcie wielokątów wypukłych...................................................o............................... 268 7.2.2. Przecięcie wielokątów gwiazdokształtnych...................................................o................. 273 7.2.3. Przecięcie odcinków ...................................................o.................................................... 274 7.2.4. Przecięcie półpłaszczyzn...................................................o.............................................. 283 7.2.5. Dwuzmienne programowanie liniowe ...................................................o........................ 285 7.2.6. Jądro wielokąta płaskiego...................................................o............................................294 7.3. Zastosowania trójwymiarowe...................................................o............................................... 300 7.3.1. Przecięcia wielościanów wypukłych ...................................................o........................... 300 7.3.2. Przecinanie półprzestrzeni..................................................o............................................308 ......... 313 ................ 315 7.4. Uwagi i komentarze...................................................o...................................................o.. 7.5. Ćwiczenia...................................................o...................................................o........... 8 Geometria prostokątów...................................................y.................................317 8.1. Wybrane zastosowania geometrii prostokątów...................................................o.................... 317 8.1.1. Wspomaganie projektowania VLSI...................................................o.............................. 317 8.1.2. Wielodostęp w bazach danych ...................................................o.................................... 319 8.2. Dziedzina poprawności wyników...................................................o......................................... 321 8.3. Ogólne uwagi o algorytmach modelu statycznego...................................................o............... 323 8 SPIS TREŚCI 8.4. Miara i obwód sumy prostokątów...................................................o........................................ 325 8.5. Kontur sumy prostokątów...................................................o.................................................... 332 8.6. Domknięcie sumy prostokątów ...................................................o............................................339 8.7. Zewnętrzny kontur sumy prostokątów ...................................................o................................ 343 8.8. Przecięcia prostokątów i podobne problemy...................................................o........................ 348 8.8.1. Przecięcia prostokątów...................................................o................................................ 348 8.8.2. Jeszcze raz problem przecięcia prostokątów ...................................................o............... 352 8.8.3. Zawieranie prostokątów...................................................o.............................................. 355 ......... 360 ............... 361 8.9. Uwagi i komentarze...................................................o...................................................o.. 8.10. Ćwiczenia ...................................................o...................................................o.......... Literatura ...................................................y...................................................y......363 Skorowidz...................... ...................................................y.................................375 1 Wprowadzenie 1.1. Rys historyczny Geometria starożytnych Egipcjan i Greków to dzieła sztuki matematyki stosowanej. Pro- blemy geometryczne pojawiały się w związku z koniecznością dokładnego wyliczania różnych obciążeń o charakterze podatkowym czy podczas wznoszenia monumentalnych budowli. Jak to nieraz w historii bywa, matematyka — stworzona jako narzędzie przy- datne faraonom w rządzeniu państwem — wyrosła znacznie ponad pierwotnie stawiane przed nią zadania, a geometria stała się szkołą myślenia matematycznego. To w geometrii tak przydatna jest zwykła intuicja, a nowe odkrycia są w zasięgu nawet amatorów. Powszechnie uważa się, że najważniejszym wkładem Euklidesa w rozwój geometrii jest przedstawienie metody aksjomatycznego przeprowadzania dowodów. Nie będziemy tutaj z tą tezą dyskutować. Dla nas jednak znacznie ważniejsze będzie pojęcie konstrukcji euklidesowej: metody obejmującej algorytm konstrukcji wraz z dowodem. Konstrukcje eukli- desowe spełniają wszystkie wymogi stawiane przed algorytmami: są jednoznaczne, po- prawne i skończone. W późniejszych czasach jednak, o ile przez 2000 lat geometria była nadal rozwijana, o tyle algorytmika została na długo zapomniana. Częściowym wyja- śnieniem takiego stanu rzeczy może być skuteczność innej metody dowodzenia — dowo- dzenia przez sprowadzenie do absurdu. Metoda ta ułatwia dowodzenie, że jakiś obiekt istnieje. Dowód prowadzi się przez zaprzeczenie, nie podaje się natomiast konkretnego sposobu konstrukcji (czyli algorytmu). Konstrukcje euklidesowe jeszcze z innego powodu zasługują na uwagę: opisano w nich zestaw środków, z jakich wolno korzystać (linijka i cyrkiel), oraz zdefiniowano zestaw dopuszczalnych czynności elementarnych. Starożytni najbardziej zainteresowani byli tym, czy przyjęte czynności elementarne są domknięte ze względu na konstrukcje skończone. Szczególnie interesowało ich, czy możliwe jest za ich pomocą zrealizowanie wszystkich dających się wymyślić konstrukcji geometrycznych, takich jak trysekcja kąta. Dzisiaj to samo pytanie moglibyśmy sformułować inaczej: czy elementarne czynności konstrukcji euklidesowych wystarczą do wykonania wszystkich możliwych „obliczeń” geometrycz- nych? Próbując odpowiedzieć na to pytanie, rozważano różne alternatywne metody, z wy- korzystaniem innych operacji i innych narzędzi. Archimedes przedstawił (poprawną zresztą) konstrukcję trysekcji kąta 60°, przy czym skorzystał z następującego rozszerzenia zbioru 14 1. WPROWADZENIE dopuszczalnych operacji: Jeśli mamy dwa okręgi, A i B, oraz punkt P, wolno nam na liniale zaznaczyć odcinek MN i umieścić go tak, aby liniał przechodził przez P, stykając się z okręgiem A w punkcie M i z okręgiem B w punkcie N. Czasami badano też ograniczony zbiór narzędzi, na przykład rozważano posługiwanie się jedynie cyrklami. Tego typu próby kojarzyć się muszą z teorią automatów, w której siłę poszczególnych modeli obliczeniowych badamy, nakładając różne ograniczenia. Niestety, dowód niezupełności zbioru narzędzi eukli- desowych pojawił się dopiero po stworzeniu i rozwinięciu algebry. Wpływ „Elementów” Euklidesa na przyszłe pokolenia był tak duży, że aż do cza- sów Kartezjusza nikt nie proponował nawet innego sformułowania geometrii. Dopiero Kartezjusz, wprowadzając swój układ współrzędnych, umożliwił skorzystanie z osiągnięć algebry, co dopiero pozwoliło zająć się krzywymi wyższych rzędów i otworzyło drogę dla rachunku Newtona. Użycie współrzędnych znacznie zwiększa możliwości oblicze- niowe, zasypując przepaść między algebrą i geometrią. Metody obliczeniowe oznaczały też renesans myślenia konstruktywistycznego. Możliwe stało się tworzenie nowych figur geometrycznych przez rozwiązywanie powiązanych z nimi równań. Już wkrótce znów pojawiły się pytania o obliczalność. Gauss, korzystając z narzędzi algebraicznych, wykazał, które wielokąty foremne mające liczbę boków wyrażonych liczbą pierwszą można zbudo- wać, korzystając z narzędzi euklidesowych. Jasne stało się, że konstrukcje wykonywane za pomocą linijki i cyrkla, wyliczanie pól i równania algebraiczne są ściśle ze sobą po- wiązane. W swej rozprawie doktorskiej Gauss wykazał, że każde równanie algebraiczne ma przynajmniej jeden pierwiastek (jest to podstawowe twierdzenie algebry). W 1828 roku Abel rozważał ten sam problem w ograniczonym modelu obliczeniowym: badał, czy pierwiastek każdego równania algebraicznego można wyznaczyć, korzystając jedynie z operacji arytmetycznych i pierwiastkowania n-tego stopnia. Udowodnił, że jest to nie- możliwe. O ile wszystkie liczby dające się skonstruować geometrycznie są algebraiczne1, o tyle Abel wykazał, że nie wszystkie liczby algebraiczne dają się skonstruować. Niedługo później Abel pokazał, które równania algebraiczne można rozwiązać za pomocą pier- wiastków, a dzięki temu możliwe było badanie wykonalności różnych problemów geo- metrycznych, takich jak trysekcja kąta. 1.1.1. Złożoność geometrii klasycznej Wszystkie konstrukcje euklidesowe — poza najprostszymi — są bardzo złożone, a to z po- wodu elementarności dozwolonych operacji. W przeszłości wielokrotnie próbowano udo- skonalić geometrię poprzez tworzenie konstrukcji składających się z mniejszej liczby operacji elementarnych. Jednak aż do dwudziestego wieku nie potrafiono określić miary złożo- ności konstrukcji. W 1902 roku Emile Lemoine w dziele Géométrographie następująco scha- rakteryzował operacje elementarne geometrii euklidesowej [Lemoine (1902)]: (cid:10) 1 Kiedy mówimy, że „liczba daje się skonstruować”, mamy na myśli możliwość konstrukcyj- nego zbudowania odcinka o długości wyrażonej taką liczbą, kiedy dany jest odcinek jednostkowy — przyp. tłum. 1.1. RYS HISTORYCZNY 15 (1) Umieszczenie nóżki cyrkla w danym punkcie. (2) Umieszczenie nóżki cyrkla na danej prostej. (3) Narysowanie okręgu. (4) Przyłożenie brzegu linijki do danego punktu. (5) Narysowanie prostej. Łączną liczbę takich operacji wykonywanych podczas tworzenia konstrukcji nazy- wamy złożonością. Definicja taka jest bardzo bliska pojęciu złożoności obliczeniowej algo- rytmów, choć Lemoine nie powiązał bezpośrednio rozmiaru danych wejściowych (liczby danych punktów i prostych) ze złożonością konstrukcji geometrycznej. Lemoine chciał poprawić starsze konstrukcje euklidesowe, a nie tworzyć teorię ich złożoności. Wcześniej odniósł niejeden sukces; euklidesowe rozwiązanie problemu okręgów Apoloniusza wy- maga 508 kroków, zaś rozwiązanie podane przez Lemoine’a liczyło poniżej dwustu kro- ków [Coolidge (1916)]. Niestety, Lemoine nie dostrzegł wagi dowodu, że dana konstrukcja wymaga pewnej minimalnej liczby kroków. Znaczenie takiego dolnego ograniczenia liczby kroków dostrzegł Hilbert. Pracując w ograniczonym modelu, rozważał jedynie te konstrukcje, które da się zrealizować za pomocą liniału i miarki — narzędzia służącego jedynie do odkładania na prostej odcinka o zadanej długości. Nie do wszystkich konstrukcji euklidesowych taki zestaw narzędzi wystarcza. Jeśli konstrukcja daje się tak przeprowadzić, na współrzędne punktów można patrzeć jako na funkcję F danych punktów. Hilbert podał warunki konieczny i wystar- czający do tego, aby F dawała się wyliczyć za pomocą n operacji pierwiastkowania dru- giego stopnia; jest to jedno z pierwszych twierdzeń dotyczących algebraicznej złożoności obliczeniowej [Hilbert (1899)]. Wiele wskazuje na to, że różne techniki stosowane dzisiaj do analizy algorytmów były używane przez geometrów już od wieków. W roku 1672 Georg Mohr wykazał, że każda konstrukcja wykonalna linijką i cyrklem może być też zrobiona samym cyrklem, o ile zgodzimy się, aby wszystkie dane i konstruowane obiekty były wyznaczane punktami. Samym cyrklem nie można narysować linii prostej, ale można ją wskazać za pomocą dwóch punktów, powstających przy przecinaniu się okręgów. W dowodzie Mohra ważne jest to, że jest to symulacja, pozwalająca pokazać, że każdą operację, w której używamy linijki, można zastąpić skończoną liczbą operacji wykonywanych samym cyrklem. Można by zapytać, czy istnieje tu jakiś ściślejszy związek z teorią automatów. Podobnego typu wnioskiem jest stwierdzenie, że w konstrukcjach, w których używana jest linijka, można użyć linijki dowolnie małej długości, byle większej od zera. Lemoine i jego naśladowcy zajmowali się złożonością konstrukcji euklidesowych, ale warto też zapytać o to, jakiej przestrzeni te konstrukcje wymagają. Naturalną miarą potrzebnej przestrzeni jest jej powierzchnia. Używana przestrzeń zależy od powierzchni wielokąta wypukłego obejmującego potrzebne punkty, powierzchni spodziewanego wyniku oraz powierzchni potrzebnej podczas konstrukcji obiektów pomocniczych [Eves (1972)]. Co warte odnotowania, zapis czasu i powierzchni nie są geometrii całkiem obce. Wprawdzie Galois wykazał niewykonalność pewnych konstrukcji euklidesowych, wobec czego niemożliwa była na przykład dokładna trysekcja kąta, nie wpływa to jednak na możliwość realizacji konstrukcji przybliżonych. Tak naprawdę zbieżne asymptotycznie procedury kwadratury koła i podwojenia sześcianu znane były już starożytnym Grekom [Heath (1921)]. Jak widać, algorytmy iteracyjne mają już naprawdę długą historię. 16 1. WPROWADZENIE 1.1.2. Teoria zbiorów wypukłych, geometria metryczna i kombinatoryczna W dziewiętnastym wieku geometria rozwijała się w wielu różnych kierunkach. Jeden z tych kierunków, zapoczątkowany przez Kleina, dotyczył badań nad zachowaniem się obiektów geometrycznych poddanych różnym przekształceniom. Innym ważnym kierunkiem roz- woju była geometria rzutowa (zobacz punkt 1.3.2). Badanie skończonych przestrzeni rzuto- wych prowadzi do fascynujących pytań z dziedziny kombinatoryki i algorytmów dyskret- nych, ale nie będziemy w tej książce zajmować się tymi dziedzinami geometrii. Rozwój analizy rzeczywistej miał duży wpływ na geometrię, gdyż dał formalne pod- stawy pojęć, które wcześniej były jedynie intuicyjne. Dwa stworzone tak dzieła — geo- metria metryczna i teoria wypukłości — stanowią bardzo ważne narzędzia matematyczne pozwalające projektować szybkie algorytmy. Odległość to jedno z podstawowych pojęć geometrii. Jego uogólnieniem jest metryka, która pozwala wprowadzić zagadnienia i metody geometryczne do analizy; „odległość” między funkcjami pozwala tworzyć przestrzenie funkcji i inne zaawansowane konstrukcje. Niestety, wiele twierdzeń tej dziedziny to twierdzenia niekonstrukcyjne. Przestrzenie funkcyjne z samej swej natury nie poddają się obliczeniom. Znaczenie teorii wypukłości polega na tym, że zajmujemy się właściwościami global- nymi, co pozwala rozwiązywać problemy ekstremów. Niestety, wiele zagadnień trudno jest sformułować algebraicznie i znów wiele twierdzeń to twierdzenia niekonstrukcyjne. Geometria kombinatoryczna w swej naturze jest znacznie bliższa geometrii algoryt- micznej. Obiekty geometryczne są w niej charakteryzowane przez właściwości podzbiorów skończonych. Przykładowo, zbiór jest wypukły wtedy i tylko wtedy, gdy odcinek wyzna- czony przez dowolne dwa punkty tego zbioru jest w tym zbiorze całkowicie zawarty. Nieprzydatność geometrii kombinatorycznej do naszych rozważań wynika stąd, że zwy- kle liczba skończonych podzbiorów jest nieskończona, co wyklucza podejście algebraiczne. Ostatnie prace nad algorytmami geometrycznymi zmierzały do usunięcia tych niedo- godności i stworzenia matematyki dającej w wyniku dobre algorytmy. 1.1.3. Wcześniejsze prace Algorytmy geometryczne były tworzone w różnych kontekstach, zaś terminu „geometria obliczeniowa” używano przynajmniej w dwóch różnych znaczeniach. Teraz postaramy się wszystkie te wysiłki ułożyć we właściwy sposób i pokazać ich miejsce w dzisiej- szej nauce. (1) Modelowanie geometryczne za pomocą krzywych i powierzchni składanych. Zagad- nienie to bliższe jest analizie numerycznej niż geometrii. Największe sukcesy odnieśli tutaj Bézier, Forrest i Riesenfeld. Warto zauważyć, że Forrest tę właśnie dziedzinę wiedzy określa mianem „geometrii obliczeniowej” [Bézier (1972), Forrest (1971), Riesenfeld (1973)]. (2) We wspaniałej książce Perceptrons Minsky i Papert (1969) opisali złożoność predykatów pozwalających rozpoznawać pewne własności geometryczne, takie jak wypukłość. 1.2. WPROWADZENIE DO ALGORYTMÓW 17 Celem ich pracy było ustalenie, czy możliwe jest użycie dużych czujników, składają- cych się z prostych układów, do rozpoznawania wzorców. Ich teoria jest samodzielna i nie mieści się w tematyce tej książki. (3) Oprogramowanie graficzne i edytory rysunków są niewątpliwie miejscem, w którym stosowanych jest szereg algorytmów przedstawianych w tej książce. Jednak w tym wypadku pojawia się wiele zagadnień związanych bezpośrednio z implementacją i interfejsem użytkownika, a nie analizą algorytmów. Do tej samej klasy rozwiązań zaliczyć należy oprogramowanie sterujące obrabiarkami numerycznymi, oprogramo- wanie ploterów, systemy kartograficzne oraz oprogramowanie inżynierskie i archi- tektoniczne. (4) Pojęcie „geometria obliczeniowa” wielu osobom może kojarzyć się z dowodzeniem twierdzeń geometrycznych za pomocą komputera. Jest to fascynująca tematyka, ale znacznie więcej mówi ona o metodach dowodzenia twierdzeń niż o samej geometrii, więc nie będziemy się nią dalej zajmować. 1.1.4. Ku geometrii obliczeniowej Na to, co dzisiaj rozumiemy przez geometrię obliczeniową, złożyło się wiele obszarów za- stosowań, w których konieczne było opracowanie wydajnych algorytmów rozwiązywa- nia problemów geometrycznych. Przykładowe zagadnienia to problem komiwojażera, mi- nimalne drzewo, ukrywanie linii czy programowanie liniowe, a także mnóstwo innych. Aby pokazać przekonująco różnorodne przykłady zastosowania geometrii obliczeniowej, przed zaprezentowaniem tych problemów najpierw przedstawimy potrzebne informacje pomocnicze. W literaturze naukowej algorytmiczne studia nad wymienionymi i podobnymi pro- blemami pojawiały się w ciągu całego wieku, a szczególnie często w ostatnim dwudzie- stoleciu. Jednak dopiero ostatnio podjęto systematyczne badania algorytmów geometrycz- nych, a zarazem zwiększyło się zainteresowanie tą dziedziną, w publikacji M. I. Shamosa (1975a) nazwaną „geometrią obliczeniową”. Mamy nadzieję, że z omawianych w tej książce zagadnień wyłoni się całościowy obraz geometrii obliczeniowej i stosowanych w niej metod. Jedną z podstawowych cech tej dzie- dziny jest stwierdzenie, że tradycyjne pojmowanie obiektów geometrycznych niejedno- krotnie nie nadaje się do projektowania optymalnych algorytmów. Aby tego problemu uniknąć, konieczne jest odnalezienie pojęć, które są przydatne w obliczeniach, i określenie ich właściwości. Krótko mówiąc, geometria obliczeniowa musi przekształcać w miarę potrzeb klasyczną dziedzinę wiedzy w jej postać obliczeniową. 1.2. Wprowadzenie do algorytmów W ciągu ostatnich piętnastu lat analiza i projektowanie algorytmów programów było jedną z najdynamiczniej rozwijających się dziedzin informatyki. Fundamentalne prace Knutha (1968, 1973) oraz Aho, Hopcrofta i Ullmana (1974) wprowadziły porządek w bogatym 18 1. WPROWADZENIE zbiorze odrębnych wyników, określiły podstawowe paradygmaty i ustaliły metodologię, która stała się standardem. Dalsze prace [Reingold-Nievergelt-Deo (1977), Wirth (1976)] jeszcze bardziej wzmocniły podstawy teoretyczne. Dokładne omawianie tych doskonałych prac wykracza poza zakres niniejszej książki, ale zakładamy, że tematyka ta jest już znana Czytelnikowi. Jednak warto, choćby z uwagę na terminologię, krótko omówić składniki języka, którym będziemy opisywali geometrię obliczeniową. Składniki te to algorytmy i struktury danych. Algorytmy to programy prze- znaczone do wykonywania na odpowiedniej abstrakcji maszyn von Neumanna. Struktury danych to sposoby ułożenia informacji, które w połączeniu z algorytmami pozwalają wydajnie i elegancko rozwiązywać problemy obliczeniowe. 1.2.1. Algorytmy: zapis i określanie wydajności Algorytmy zapisuje się z uwzględnieniem konkretnego modelu obliczeniowego. Jak zoba- czymy w podrozdziale 1.4, model obliczeniowy to wygodna abstrakcja maszyny fizycznej stosowanej do wykonywania programów. Jak jednak wykazali Aho-Hopcroft-Ullman (1974), nie jest konieczne ani pożądane zapisywanie algorytmu w formie kodu maszy- nowego. Zamiast tego, aby zachować jasność, zwięzłość i zapewnić zrozumiałość zapisu, należy zwykle2 użyć wysokopoziomowego języka Pidgin Algol, który stał się już stan- dardem w literaturze przedmiotu. Pidgin Algol to nieformalna i elastyczna wersja języka podobnego do Algolu. Zapis struktur kontrolnych jest ściśle określony, ale wszelkie inne wyrażenia można zapisywać bardzo dowolnie, ścisły zapis matematyczny może być mie- szany z językiem naturalnym. Oczywiście, programy w języku Pidgin Algol mogą być automatycznie przekładane na programy zapisane w formalnych językach wysokiego poziomu. Podobnie jak Aho-Hopcroft-Ullman, pokażemy konstrukcje języka Pidgin Algol. Formalne deklaracje typów danych nie mają tu zastosowania, zaś typ zmiennej zwykle jasno wynika z kontekstu. Poza tym nie ma żadnego specjalnego formatu zapisu wyra- żeń i warunków. Program nazywamy procedurą, ma on postać: procedure nazwa (parametry) instrukcja. Instrukcję można zapisać jako łańcuch dwóch lub więcej instrukcji, ujęty w „nawiasy” „begin…end”: begin instrukcja; ... instrukcja end. (cid:10) 2 Czasami algorytmy mogą być zapisywane w formie zwykłego tekstu. 1.2. WPROWADZENIE DO ALGORYTMÓW 19 Instrukcja może też mieć postać zdania języka naturalnego lub jedną z poniższych postaci: (1) Przypisanie: zmienna := źródło wartości „Źródło wartości” to opis wyliczenia wartości, która ma być przypisana zmiennej. Wyliczenie to, ogólnie rzecz biorąc, wyrażenie na zbiorze zmiennych (niektóre z tych zmiennych mogą być zapisane jako „funkcje”; funkcja to przypadek szczególny pro- gramu, co pokażemy dalej). (2) Instrukcja warunkowa: if warunek then instrukcja (else instrukcja) Część z else jest opcjonalna. (3) Pętla — może mieć jedną z trzech postaci: 3a. for zmienna := wartość until wartość do instrukcja 3b. while warunek do instrukcja 3c. repeat instrukcja until warunek Konstrukcje while i repeat różnią się o tyle, że w przypadku pętli while warunek jest sprawdzany przed wykonaniem instrukcji, zaś w pętli repeat najpierw wykony- wana jest instrukcja. (4) Instrukcja powrotu: return wyrażenie Instrukcja tego typu musi pojawić się w programach będących funkcjami. Programy takie mają postać: function nazwa (parametry) instrukcja. Wyrażenie będące argumentem return staje się źródłem wartości dla instrukcji przypisania, pokazanej powyżej w punkcie 1. Algorytmy zapisane w języku Pidgin Algol często zawierają komentarze, mające ułatwiać ich zrozumienie. Zwykle komentarz zapisuje się w postaci: (∗zdanie w języku naturalnym∗). Czas potrzebny na obliczenia — czyli wykonanie algorytmu — to suma czasów wy- konywania poszczególnych operacji (zobacz też podrozdział 1.4). Jak już wcześniej wspo- mnieliśmy, w Pidgin Algolu program można łatwo przekształcić na kod maszynowy 20 1. WPROWADZENIE wybranego komputera (choć zadanie to może być żmudne). W zasadzie byłaby to metoda wyznaczenia czasu wykonywania programu. Jednak jest to rozwiązanie nie tylko żmudne, ale i mało kształcące, gdyż odwołujemy się do konkretnego komputera, podczas gdy interesuje nas zależność funkcyjna między czasem wykonania a wielkością rozwiązywa- nego problemu (czyli jak szybko rośnie czas wykonania przy wzroście wielkości pro- blemu). Wobec tego przyjęło się w analizie i projektowaniu algorytmów określać czas wykonywania (a także wszelkie inne miary szybkości działania) z pominięciem stałych współczynników. Zwykle robi się to, uwzględniając jedynie wybrane „operacje kluczowe” algorytmu (wystarcza do tego analiza algorytmu zapisanego w języku wysokiego po- ziomu). Takie podejście jest jak najbardziej uprawnione, jeśli chodzi o ustalanie dolnego ograniczenia czasu wykonania, gdyż wszystkie nieuwzględniane w takim przypadku operacje mogą czas wykonania jedynie zwiększać. Jeśli jednak chodzi o górne ograni- czenie, trzeba zapewnić, że wybrane operacje będą stanowiły stały ułamek wszystkich operacji algorytmu. Knuth spopularyzował metodę zapisu, która pozwala rozróżnić ogra- niczenie górne i dolne; w tej książce także skorzystamy z tej metody [Knuth (1976)]: • • • • O(f(N)) oznacza zbiór wszystkich funkcji g(N) takich, że istnieją stałe dodatnie C i N0, że dla wszystkich N ≥ N0 zachodzi |g(N)| ≤ Cf(N). Ω(f(N)) oznacza zbiór wszystkich funkcji g(N) takich, że istnieją dodatnie stałe C i N0 takie, że dla wszystkich N ≥ N0 zachodzi g(N) ≥ Cf(N). θ(f(N)) oznacza zbiór wszystkich funkcji g(N) takich, że istnieją dodatnie stałe C1, C2 i N0 takie, że dla wszystkich N ≥ N0 zachodzi C1f(N) ≤ g(N) ≥ C2f(N). o(f(N)) oznacza zbiór wszystkich funkcji g(N) takich, że dla wszystkich dodatnich sta- łych C istnieje stała N0 taka, że dla wszystkich N ≥ N0 zachodzi g(N) ≤ Cf(N) (lub, co jest równoważne, limN→∞ g(N)/f(N) = 0). Tak więc O(f(N)) zawiera funkcje nie większe niż pewne stałe razy f(N) — tak można określić ograniczenie górne. Z kolei Ω(f(N)) zawiera funkcje nie mniejsze niż pewna stała razy f(N), więc mamy ograniczenie dolne. W końcu θ(f(N)) zawiera funkcje tego samego rzędu co f(N), przez co możemy określić algorytmy „optymalne”. Omówiliśmy już czas wykonywania algorytmu. Inną ważną miarą wydajności jest zajmowanie pamięci. Właśnie pamięć i czas, wyrażone jako funkcje wielkości problemu, stanowią dwie podstawowe miary wydajności przy analizie algorytmów. Głównym celem niniejszej książki jest przedstawienie algorytmów dotyczących pro- blemów geometrycznych i oszacowanie ich złożoności w najgorszym przypadku. Złożoność w najgorszym przypadku to największa miara wydajności algorytmu przy danej wielkości problemu. Z kolei złożoność przypadku średniego (czyli złożoność oczekiwana) to oszaco- wanie, jakiej złożoności powinniśmy spodziewać się podczas testów. Niestety, analiza przypadku średniego jest znacznie trudniejsza od analizy przypadku najgorszego. Po pierwsze, pojawiają się trudności matematyczne — nawet w przypadku dobrego doboru rozkładu parametrów. Po drugie, rzadko udaje się ustalić, jak w praktyce będzie wyglądało typowe użycie algorytmu. Dlatego właśnie zwykle analizuje się przypadek najgorszy. W niniejszej książce sporadycznie zajmować się będziemy wynikami przypadku średniego. Inną ważną rzeczą, którą należy tutaj podkreślić, jest fakt, że w zapisie „rzędu złożo- ności” nie pojawiają się współczynniki mnożenia. Wobec tego uzyskana złożoność obowią- zuje jedynie w przypadku dostatecznie dużych problemów. Z tego powodu mówimy 1.2. WPROWADZENIE DO ALGORYTMÓW 21 w takiej sytuacji o analizie asymptotycznej. Możliwe jest — i wcale nie rzadkie — że w przy- padku małych problemów optymalny algorytm nie jest algorytmem najlepszym asymp- totycznie. Wybierając algorytm do konkretnego zastosowania, trzeba powyższe zawsze mieć na uwadze. 1.2.2. Nieco o technikach tworzenia algorytmów Wydajne algorytmy opisujące problemy geometryczne często tworzy się, przetwarzając techniki ogólne danej dziedziny, jak „dziel i rządź”, równoważenie, rekurencję czy progra- mowanie dynamiczne. Doskonałe omówienie tych technik znaleźć można w klasycznych już tekstach poświęconych analizie i projektowaniu algorytmów (na przykład [Aho-Hop- croft-Ullman (1974)]) i zbędne jest tutaj powtarzanie tego. Istnieje technika, która w sposób naturalny jest szczególnie polecana do rozwiązy- wania problemów geometrycznych. Technikę tę nazywamy wymiataniem, przy czym naj- częściej korzysta się z wymiatania płaszczyzny (w dwóch wymiarach) i wymiatania przestrzeni (w trzech wymiarach). Teraz omówimy najważniejsze cechy wymiatania płaszczyzny; uogólnienie tego do trzech wymiarów jest już proste. Aby nie być gołosłownym, pokażemy tę metodę na konkretnym przykładzie (który dokładniej omówimy w punkcie 7.2.3): jeśli mamy dany zbiór odcinków na płaszczyźnie, należy znaleźć wszystkie ich przecięcia. Rozważmy prostą l (bez utraty ogólności możemy założyć, że jest ona pionowa), która dzieli płaszczyznę na lewą i prawą półpłaszczyznę. Załóżmy, że każda z tych półpłaszczyzn zawiera końce danych odcinków. Jest jasne, że rozwiązaniem naszego zadania będzie suma rozwiązań dla wszystkich takich par pół- płaszczyzn. Zakładając zatem, że mamy już zbiór przecięć na lewo od l, wiemy, że na uzyskany zbiór nie będą miały wpływu odcinki znajdujące się na prawo od l. Zauważmy, że przecięcie może wystąpić jedynie między dwoma takimi odcinkami, których przecięcia z pewną pionową prostą przylegają do siebie. Tak więc, jeśli uwzględnimy wszystkie pionowe przecięcia danego zbioru odcinków, odnajdziemy wszystkie przecięcia. Jako że jednak niemożliwe jest wyliczenie ciągłego, nieskończonego zbioru wszystkich przecięć pionowych, musimy ten problem rozwiązać inaczej. Zauważmy, że płaszczyzna dzielona jest na pionowe paski, z których każdy ograniczony jest albo końcami odcinków, albo przecięciami odcinków, przy czym pionowa kolejność odcinania przez pionowe cięcie jest stała. Wobec tego wystarczy przejść od lewego brzegu takiego paska do jego brzegu prawego, zaktualizować kolejność odcinków i sprawdzić, czy między „przylegającymi” odcinkami występują jakieś nowe przecięcia. W powyższym omówieniu pokazaliśmy podstawowe cechy techniki wymiatania płasz- czyzny. Pionowa prosta przesuwana jest po płaszczyźnie od lewej do prawej, przy czym zatrzymuje się w punktach szczególnych, nazywanych „punktami zdarzeń”. Przecięcie tej prostej z badanymi danymi zawiera wszystkie informacje potrzebne do przejścia dalej. Tak więc mamy dwie podstawowe struktury: (1) Harmonogram punktów zdarzeń, który określa ciąg współrzędnych odciętych, upo- rządkowany od lewej do prawej — w ten sposób definiujemy punkty zatrzymania linii wymiatającej. Zwróćmy uwagę, że harmonogram punktów zdarzeń nie musi 22 1. WPROWADZENIE od razu wynikać z danych wejściowych, ale może być aktualizowany dynamicznie podczas wykonywania algorytmu wymiatania płaszczyzny. W różnych zastosowa- niach potrzebne mogą być różne struktury danych. (2) Stan prostej wymiatającej, który odpowiada opisowi przecięcia linii wymiatającej z geometryczną strukturą wymiataną. Owo odpowiadanie oznacza, że przecięcie zawiera informacje charakterystyczne dla danego zastosowania. Stan prostej wymia- tającej jest aktualizowany przy przyjściu do każdego następnego punktu; każdora- zowo konieczne jest też wybieranie odpowiedniej struktury danych. Przykłady algorytmów wymiatania płaszczyzny pokażemy w punkcie 2.2.2. 1.2.3. Struktury danych W algorytmach geometrycznych mamy do czynienia z przetwarzaniem obiektów, które nie są obsługiwane bezpośrednio na poziomie języka maszynowego. Wobec tego użytkownik musi te złożone obiekty opisać za pomocą prostszych typów danych, które są dla kom- putera zrozumiałe. Opisy tego typu określamy mianem struktur danych. Najpowszechniej spotykanymi obiektami złożonymi w algorytmach geometrycznych są zbiór i ciąg (uporządkowany zbiór). Struktury danych najlepiej je opisujące omówiono w literaturze podstawowej o algorytmach i do niej kierujemy Czytelnika [Aho-Hopcroft- -Ullman (1974), Reingold-Nievergelt-Deo (1977)]. Nam wystarczy jedynie wymienienie dostępnych struktur danych oraz opisanie ich działania i wpływu na wydajność. Niech S będzie zbiorem reprezentowanym przez strukturę danych, a u niech będzie dowolnym elementem zbioru, którego S jest podzbiorem. Podstawowe operacje na zbio- rach to: (1) MEMBER(u, S). Czy u ∈ S? (odpowiedź: TAK lub NIE). (2) INSERT(u, S). Dodanie u do S. (3) DELETE(u, S). Usunięcie u z S. Załóżmy, że {S1, S2, …, Sk} to zbiór zbiorów (parami rozłącznych). Przydatnymi ope- racjami na takim zbiorze zbiorów są: (4) FIND(u). Podanie j, jeśli u ∈ Sj. (5) UNION(Si, Sj; Sk). Tworzona jest suma zbiorów Si i Sj, oznaczana jako Sk. Kiedy zbiór zewnętrzny jest całkowicie uporządkowany, bardzo ważne są następu- jące operacje: (6) MIN(S). Podanie najmniejszego elementu z S. (7) SPLIT(u, S). Zbiór S dzielony jest na {S1, S2} takie, że S1 = {v: v ∈ S oraz v ≤ u} oraz S2 = S–S1. (8) CONCATENATE(S1, S2). Zakładając, że dla dowolnych u ∈ S1 i u” ∈ S2 mamy u ≤ u”, tworzymy uporządkowany zbiór S = S1 ∪ S2. 1.2. WPROWADZENIE DO ALGORYTMÓW 23 Struktury danych można pogrupować ze względu na operacje, jakie są w nich możliwe (abstrahując od szybkości wykonywania tych operacji). Tak więc w przypadku zbiorów uporządkowanych mamy następującą tabelę: TABELA I Struktura danych Obsługiwane operacje Słownik Kolejka priorytetowa Kolejka łączona MEMBER, INSERT, DELETE MIN, INSERT, DELETE INSERT, DELETE, SPLIT, CONCATENATE Z uwagi na wydajność wszystkie te struktury danych zwykle realizuje się jako zbilanso- wane drzewo binarne (często AVL albo 2- lub 3-drzewo) [Aho-Hopcroft-Ullman (1974)]. W ten sposób każda operacja jest wykonywana w czasie proporcjonalnym do logarytmu liczby elementów zapisanych w strukturze danych. Ilość zajmowanej pamięci jest pro- porcjonalna do wielkości zbioru. Na powyższe struktury danych można spojrzeć bardziej abstrakcyjnie, jako na liniowe tablice (czyli listy), gdzie wstawienia i usunięcia można wykonywać na dowolnych po- zycjach takiej tablicy. W niektórych zastosowaniach bardziej odpowiednie są ograniczone, uproszczone tryby dostępu. Strukturami takimi są: kolejki, w których wstawianie ma miejsce na końcu, a usunięcie na drugim końcu; stosy, gdzie wstawianie i usuwanie ma miejsce na jednym końcu (szczycie stosu). Jasne jest, że zarządzanie stosem i kolejką wymaga użycia odpowiednio jednego i dwóch wskaźników. Aby skrócić zapis, mając na myśli dodanie i usunięcie z U, będziemy używać odpowiednio symboli „⇒U” oraz „U⇒”, gdzie U jest kolejką lub stosem. Zbiory nieuporządkowane zawsze można traktować tak samo, jak zbiory uporządko- wane, sztucznie ustalając porządek elementów (na przykład przypisując elementom „na- zwy” i stosując kolejność alfabetyczną). Typową strukturą danych w takim przypadku jest: TABELA II Struktura danych Obsługiwane operacje Sterta łączona INSERT, DELETE, FIND, UNION, (MIN) Każda z powyższych operacji wykonywana jest w czasie O (logN), gdzie N jest rozmia- rem zbioru w strukturze danych, przy czym całość implementowana jest jako zrów- noważone drzewo. Jeśli elementy rozważanego zbioru będą reprezentowane jako liczby całkowite od 1 do N, możliwe jest dopracowanie struktury danych tak, aby N operacji na zbiorze o rozmiarze N było wykonywanych w czasie O(N ⋅ A (N)), gdzie A(N) jest wyjąt- 1622 kowo wolno rosnącą funkcją, związaną z funkcją Ackermanna (przykładowo dla N ≤ , czyli ∼1020 000, A(N) ≤ 5). Przedstawione powyżej typowe struktury danych są bardzo często używane w algo- rytmach geometrii obliczeniowej. Jednak z natury problemów geometrycznych wynikła konieczność stworzenia specyficznych, nietypowych struktur danych, z których dwie są tak powszechnie stosowane i przydatne, że na miejscu będzie ich opisanie w tym roz- dziale wstępnym. Są to drzewo przedziałów i podwójnie powiązana lista krawędzi. 24 1. WPROWADZENIE 1.2.3.1. Drzewo przedziałów Drzewo przedziałów, pierwotnie wprowadzone przez J. L. Bentleya [Bentley (1977)], jest strukturą danych, służącą do zapisu przedziałów prostej rzeczywistej, których końce należą do ustalonego zbioru N odciętych. Jako że zbiór odciętych jest ustalony, drzewo przedziałów jest strukturą statyczną z uwagi na odcięte, których nie można dodawać ani usuwać. Poza tym odcięte mogą być znormalizowane przez zastąpienie ich numerem liczonym od lewej do prawej. Nie tracąc ogólności, można rozważać te odcięte jako liczby całkowite z zakresu [1, N]. Drzewo odcinków to drzewo binarne z korzeniem. Jeśli mamy liczby całkowite l i r, przy czym l r, drzewo przedziałów T(l, r) buduje się rekurencyjnie: ma ono korzeń v, parametry B[v] = l oraz E[v] = r (B i E to skróty od angielskich słów Beginning i End, odpo- wiednio „początek” i „koniec”) oraz — jeśli r–l 1 — drzewo to ma lewe poddrzewo T(l, (B[v]+E[v]/2) oraz poddrzewo prawe T((B[v]+E[v]/2, r). Korzenie tych dwóch poddrzew oznacza się jako LSON[v] i RSON[v]. Parametry B[v] i E[v] określają przedział [B[v], E[v]] ⊆ [l, r], powiązany z węzłem v. Drzewo przedziałów pokazano na rysunku 1.1. Zbiór przedziałów {[B[v], E[v]]: v jest węzłem T(l, r)} to przedziały standardowe T(l, r). 3. Przedziały standardowe należące do liści T(l, r) nazywamy przedziałami elementarnymi Łatwo wykazać, że T(l, r) jest zrównoważone (wszystkie liście należą do kolejnych prze- działów, a jego wysokość to log2(r–l). RYSUNEK 1.1. Drzewo przedziałów T(4, 15) Drzewo przedziałów T(l, r) służy do zapisu przedziałów, których końce należą do zbioru {l, l+1,…, r} w sposób dynamiczny, czyli z możliwością dodawania i usuwania. W szczegól- ności dla r–l 3 dowolny przedział [b, e] z liczbami całkowitymi b e zostanie podzielony na zbiór najwyżej log2(r–l)+log2(r–l –2 przedziałów standardowych T(l, r). Podział prze- działu [b, e] jest całkowicie zdefiniowany przez operację zapisującą (wstawiającą) [b, e] do drzewa T, czyli przez następujące wywołanie INSERT(b, e; korzeń(T)): procedure INSERT(b, e; v) begin if (b ≤ B[v]] and (E[v] ≤ e) then wstaw [b, e] do v else begin if(b (B[v]+E[v])/2) then INSERT(b, e; LSON[v]); if((B[v]+E[v])/2 e) then INSERT(b, e;RSON[v] end end. (cid:10) 3 Ściśle rzecz biorąc, przedział związany z v jest częściowo domkniętym przedziałem [B[v], E[v]]; wyjątkiem są końcowe prawe węzły T(l, r), których przedziały są domknięte. 1.2. WPROWADZENIE DO ALGORYTMÓW 25 Wywołaniu INSERT(b, e; korzeń(T)) odpowiada „przejście” po T, którego ogólna struktura jest taka, jak to pokazano na rysunku 1.2. Ścieżka początkowa może być pusta — ozna- czamy ją jako PIN; przechodzi ona od korzenia do węzła v*. Węzeł ten nazywamy rozga- łęzieniem, gdyż od niego zaczynają się dwie ścieżki PL i PR (które mogą być puste). Nie- zależnie od tego, czy wstawiany przedział jest całkowicie umieszczony w rozgałęzieniu (kiedy PL i PR są puste), wszystkie prawe węzły potomne PL nie należące do PL, jak rów- nież wszystkie lewe węzły potomne PR nie należące do PR identyfikują fragmentację [b, e] (węzły alokacji). RYSUNEK 1.2. Wstawianie przedziału [74, 107] do T(1, 257). Węzły alokacji zostały obwiedzione podwójnym kółkiem Alokacja przedziału w węźle v z T może mieć inną postać, zależną od wymagań w konkretnym zastosowaniu. Często wystarczy znać liczbę elementów zbioru przedziałów alokowanych w danym węźle v; wystarczy do tego pojedynczy parametr C[v], będący nie- ujemną liczbą całkowitą i oznaczający liczbę elementów; tak więc alokacja [b, e] w v staje się C[v] := C[v]+1. W innych zastosowaniach konieczne jest zachowanie tożsamości przedziałów alokowanych w węźle v. Następnie dołączamy do każdego węzła v z T pomocniczą strukturę — listę L[v], której elementy są identyfikatorami przedziałów. Operacją symetryczną do INSERT jest DELETE, zapisywana następująco (zakładamy, że interesuje nas zapamiętanie parametru C[v]): 26 1. WPROWADZENIE procedure DELETE(b, e; v) begin if (b ≤ B[v]) and (E[v] ≤ e) then C[v] := C[v]–1 else begin if (b (B[v]+E[v])/2) then DELETE(b, e; LSON[v]); if ((B[v]+E[v])/2 e) then DELETE(b, e; RSON[v]); end end. Zauważmy, że jedynie usuwanie przedziałów wcześniej wstawionych gwarantuje nam po- prawność działań. Drzewo przedziałów jest wyjątkowo wszechstronną strukturą danych, o czym prze- konać się będziemy mogli w wielu przykładach zastosowań (rozdziały 2. i 8.). Zauważmy jeszcze tylko, że jeśli chcemy wiedzieć, ile przedziałów zawiera dany punkt x, wystarczy zwykłe wyszukiwanie binarne w T (czyli przejście ścieżki od korzenia do liścia). 1.2.3.2. Podwójnie powiązana lista krawędzi Podwójnie powiązana lista krawędzi (oznaczana jako DCEL, od angielskiej nazwy doubly-connected-edge-list) świetnie nadaje się do zapisu grafów płaskich, umieszczonych na płaszczyźnie [Muller-Preparata (1978)]. Zanurzenie w płaszczyźnie grafu płaskiego G = (V, E) to odwzorowanie wszystkich węzłów z V na punkty płaszczyzny i wszystkich krawędzi z E na krzywe łączące obrazy dwóch węzłów, które dana krawędź łączy; odwzo- rowanie jest tak dobrane, że żadne krawędzie nie przecinają się nigdzie poza swoimi końcami. Wiadomo powszechnie, że wszystkie grafy płaskie można tak zanurzyć w płasz- czyźnie, aby wszystkie krawędzie były reprezentowane przez odcinki proste [Fary (1948)]. Niech V = {v1, ..., vN} oraz E = {e1, ..., eM}. Podstawowym składnikiem listy krawędzi grafu płaskiego (V, E) jest węzeł krawędzi. Między krawędziami i węzłami krawędzi istnieje odwzorowanie jeden do jednego, czyli każda krawędź reprezentowana jest dokładnie raz. Węzeł krawędzi zawiera cztery pola z wartościami: V1, V2, F1 i F2 oraz dwa wskaźniki, P1 i P2. Tak więc odpowiednią strukturę danych można bez trudu zaimplementować jako sześć tablic o takich samych nazwach, przy czym każda tablica składa się z M ko- mórek. Znaczenie pól jest następujące: V1 zawiera początek krawędzi, V2 jej koniec; tak oto krawędzi standardowo przypisywana jest orientacja. Pola F1 i F2 zawierają nazwy opisujące krawędź z V1 do V2: nazwy leżące na lewo i na prawo od krawędzi. Wskaźnik P1 (odpowiednio P2) wskazuje węzeł krawędzi, zawierający pierwszą krawędź znajdującą się za (V1, V2), przy ruchu w kierunku przeciwnym do ruchu wskazówek zegara. Jako nazwy mogą być użyte liczby całkowite. Przykładowy graf wraz z odpowiadającą mu listą DCEL pokazano na rysunku 1.3. Łatwo teraz pokazać, jak na liście DCEL można wskazać krawędzie przylegające do danego węzła lub krawędzie zamykające dany obszar. Jeśli graf ma N węzłów i F obszarów, możemy założyć, że mamy do czynienia z dwiema tablicami — HV[1:N] oraz HF[1:F] — nagłówków węzłów i listy obszarów: tablice te można wypełnić, przeglądając tablice V1 i F1 w czasie O(N). Poniższa procedura VERTEX(j) pozwala uzyskać listę krawędzi przy- legających do vj w formie ciągu adresów z tablicy A. 1.2. WPROWADZENIE DO ALGORYTMÓW 27 RYSUNEK 1.3. Przykład listy DCEL procedure VERTEX(j) begin a := HV[j]; a0 := a; A[1] := a; i := 2; if (V1[a] = j) then a := P1[a] else a := P2[a]; while (a ≠ a0) do begin A[i] := a; if (V1[a] = j) then a := P1[a] else a := P2[a]; i := i+1 end end. VERTEX(j) wykonuje się w czasie proporcjonalnym do liczby krawędzi przylegających do vj. Analogicznie możemy stworzyć procedurę FACE(j), pobierającą ciąg krawędzi zamyka- jących fj; wystarczy zamienić HV i V1 na HF i F1 w powyższej procedurze VERTEX(j). Zauważmy, że procedura VERTEX bada krawędzie w kierunku przeciwnym do ruchu wskazówek zegara, podczas gdy FACE bada je dookoła obszaru w kierunku zgodnym z ruchem wskazówek zegara. Często graf płaski G = (V, E) zapisuje się jako listę krawędzi, gdzie dla każdego węzła vj ∈ V wskazuje się listę krawędzi przylegających ułożonych tak, jak są ułożone dookoła vj w kierunku przeciwnym do ruchu wskazówek zegara. Łatwo pokazać, że zapis G w formie listy krawędzi można przekształcić na DCEL w czasie O( V ). 28 1. WPROWADZENIE 1.3. Podstawy geometrii 1.3.1. Definicje ogólne, przyjęte konwencje Obiekty, którymi zajmuje się geometria obliczeniowa, to najczęściej zbiory punktów w prze- strzeni euklidesowej4. Zakłada się użycie prostokątnego systemu współrzędnych, wobec czego każdemu punktowi odpowiada wektor w tych współrzędnych. Obiekty geometryczne nie muszą składać się ze skończonej liczby punktów, ale muszą być skończenie opisywalne (zwykle przez skończony łańcuch parametrów). Tak więc poza pojedynczymi punktami, będziemy rozważali proste zawierające dwa dane punkty, odcinki o danych końcach, płaszczyzny zawierające dane trzy punkty, wielokąty określone uporządkowanym ciągiem wierzchołków i tak dalej. W tym punkcie nie będziemy podawać formalnych definicji opisywanych pojęć; chodzi jedynie o przypomnienie najważniejszych faktów i przedstawienie stosowanego dalej zapisu. Przez E d oznaczamy d-wymiarową przestrzeń euklidesową, czyli przestrzeń d-krotek . Teraz przypomnimy defi- 2 ) ix (x1, …, xd) liczb całkowitych xi, i = 1, …, d z metryką nicje najważniejszych obiektów, którymi zajmuje się geometria obliczeniowa. (∑ 2/1 d i 1 = Punkt. d-krotka (x1, …, xd) oznacza punkt p w E towany jako d-wektor zaczepiony w początku układu współrzędnych E bodnym końcem jest punkt p. d; Punkt ten może być też zinterpre- d, którego swo- Prosta, płaszczyzna, rozmaitość liniowa. Jeśli dane są dwa różne punkty q1 i q2 należące d, to kombinacja liniowa do E α q 11 + − 1( α ) q 2 R∈α ( ) jest prostą w E cych do E d (k ≤ d), to kombinacja liniowa d. Ogólnie, jeśli danych jest k niezależnych liniowo punktów q1, …, qk należą- α q 11 + α q 2 2 + L α + ∈ j R − 1 q k k , j − ( α jest kombinacją liniową wymiaru (k–1) w E d. − + 1 1 = 1( ,..., k 1 α − )1 − L − α ) q k k 1 − Odcinek. Jeśli dane są dwa różne punkty q1 i q2 w E d, jeśli do wyrażenia αq1+(1–α)q2 dodamy warunek 0 ≤ α ≤ 1, otrzymamy wypukłą kombinację q1 i q2, czyli: q α 1 + − 1( α ) q 2 ∈ α R ( 0, ≤ ≤ α )1 (cid:10) 4 Ograniczenie się do przestrzeni euklidesowej (pewnego szczególnego, choć wyjątkowo ważnego przypadku geometrii metrycznej) pozwala nam wykorzystać intuicję, a poza tym to właśnie prze- strzeni euklidesowej dotyczy większość zastosowania. Jednak ograniczenie to nie jest tak bardzo ważne w wielu aplikacjach, które będziemy omawiać w dalszych rozdziałach. Do tego ważnego zagadnienia wrócimy jeszcze w punkcie 1.3.2. 1.3. PODSTAWY GEOMETRII 29 Kombinacja taka opisuje odcinek łączący punkty q1 i q2. Zwykle odcinek oznacza się jako 21qq (para nieuporządkowana). Zbiór wypukły. Figura D w E należących do D odcinek 21qq d jest wypukła, jeśli dla dowolnych dwóch punktów q1 i q2 jest całkowicie zawarty w D. Można wykazać, że przecięcie figur wypukłych zawsze jest figurą wypukłą. Wypukły wielokąt opisany. Wypukły wielokąt opisany zbioru punktów S w E d to najmniej- sza figura wypukła w E d, zawierająca S. Wielokąt. W E 2 wielokąt definiuje się za pomocą skończonego zbioru odcinków takich, że każdy koniec każdego odcinka jest wspólny dla dokładnie dwóch krawędzi i żaden podzbiór krawędzi nie ma takiej własności. Odcinki są krawędziami, zaś ich końce są wierzchołkami wielokąta (warto zauważyć, że krawędzi i wierzchołków jest tyle samo). Wielokąt o n wierzchołkach to n-kąt. Wielokąt jest prosty, jeśli żadna para niekolejnych krawędzi nie ma wspólnych punk- tów. Wielokąt prosty dzieli płaszczyznę na dwa rozdzielne podzbiory: wnętrze (ograni- czone) oraz zewnętrze (nieograniczone), które są rozdzielone wielokątem (twierdzenie Jordana o krzywej). Pamiętajmy, że w mowie potocznej mówiąc o wielokącie, mamy zwykle na myśli sumę brzegu i wnętrza. Wielokąt prosty jest wypukły, jeśli wypukłe jest jego wnętrze. Wielokąt prosty P jest gwiazdokształtny, jeśli istnieje punkt z nie zewnętrzny do P taki, że dla wszystkich punktów p z P odcinek zp jest całkowicie zawarty w P (tak więc wszystkie wielokąty wypukłe są jednocześnie gwiazdokształtne). Położenie punktu z, mającego opisaną właściwość, określa jądro P. Wobec tego wielokąt wypukły jest swoim własnym jądrem. Graf płaski. Graf G = (V, E) zbiór węzłów V, zbiór krawędzi E) jest płaski, jeśli można zanurzyć go w płaszczyźnie unikając przecięć (punkt 1.2.3.2) Zanurzenie grafu płaskiego o prostych krawędziach w płaszczyźnie określa podział płaszczyzny nazywany podziałem płaskim lub mapą. Niech v, e i f oznaczają odpowiednią liczbę węzłów, krawędzi i obszarów (łącznie z jednym obszarem nieograniczonym) dla podziału. Owe trzy wielkości powią- zane są ze sobą klasycznym wzorem Eulera [Bollobás (1979)]: +− ev 2= f (1.1) Jeśli mamy dodatkową właściwość polegającą na tym, że wszystkie węzły są stopnia ≥ 3, to łatwo jest udowodnić następujące nierówności: e , ≤ 3 v − 6 e ≤ v ≤ e 2 3 3 − ,6 f ≤ v 2 f − ,4         ≤ ≤ e 2 3 2 v f f − 4 (1.2) co pokazuje, że v, e i f są parami proporcjonalne (zauważmy też, że trzy nierówności z prawej strony są prawdziwe bezwarunkowo). 30 1. WPROWADZENIE Triangulacja. Podział płaski jest triangulacją, je
Pobierz darmowy fragment (pdf)

Gdzie kupić całą publikację:

Geometria obliczeniowa. Wprowadzenie
Autor:
,

Opinie na temat publikacji:


Inne popularne pozycje z tej kategorii:


Czytaj również:


Prowadzisz stronę lub blog? Wstaw link do fragmentu tej książki i współpracuj z Cyfroteką: