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
Wstęp do wydania drugiego (9)Wstęp (11)
1. Wprowadzenie (13)
- 1.1. Rys historyczny (13)
- 1.1.1. Złożoność geometrii klasycznej (14)
- 1.1.2. Teoria zbiorów wypukłych, geometria metryczna i kombinatoryczna (16)
- 1.1.3. Wcześniejsze prace (16)
- 1.1.4. Ku geometrii obliczeniowej (17)
- 1.2. Wprowadzenie do algorytmów (17)
- 1.2.1. Algorytmy: zapis i określanie wydajności (18)
- 1.2.2. Nieco o technikach tworzenia algorytmów (21)
- 1.2.3. Struktury danych (22)
- 1.3. Podstawy geometrii (28)
- 1.3.1. Definicje ogólne, przyjęte konwencje (28)
- 1.3.2. Niezmienniki grup przekształceń liniowych (30)
- 1.3.3. Dualność geometryczna. Biegunowość (35)
- 1.4. Modele obliczeniowe (37)
- 2.1. Wprowadzenie do przeszukiwania geometrycznego (47)
- 2.2. Problemy lokalizacji punktu (51)
- 2.2.1. Rozważania ogólne. Najprostsze przypadki (51)
- 2.2.2. Lokalizacja punktu w obszarze płaszczyzny (55)
- 2.3. Problemy związane z przeszukiwaniem zakresu (78)
- 2.3.1. Rozważania ogólne (78)
- 2.3.2. Metoda wielowymiarowego drzewa binarnego (k-D drzewa) (83)
- 2.3.3. Metoda bezpośredniego dostępu i jej odmiany (87)
- 2.3.4. Metoda drzew zakresu i jej odmiany (91)
- 2.4. Szukanie iterowane i kaskadowanie ułamkowe (96)
- 2.5. Uwagi i komentarze (99)
- 2.6. Ćwiczenia (101)
- 3.1. Informacje wstępne (103)
- 3.2. Sformułowanie problemu i ograniczenia dolne (107)
- 3.3. Algorytmy otoczki wypukłej na płaszczyźnie (111)
- 3.3.1. Pierwsze dokonania w dziedzinie algorytmów otoczki wypukłej (111)
- 3.3.2. Skan Grahama (114)
- 3.3.3. Marsz Jarvisa (117)
- 3.3.4. Techniki QUICKHULL (119)
- 3.3.5. Algorytmy typu "dziel i rządź" (121)
- 3.3.6. Dynamiczne algorytmy otoczki wypukłej (124)
- 3.3.7. Uogólnienie: zachowanie otoczki wypukłej (130)
- 3.4. Otoczki wypukłe w większej liczbie wymiarów niż dwa (136)
- 3.4.1. Metoda opakowywania prezentu (137)
- 3.4.2. Metoda "pod-poza" (142)
- 3.4.3. Trójwymiarowe otoczki wypukłe (145)
- 3.5. Uwagi i komentarze (150)
- 3.6. Ćwiczenia (152)
- 4.1. Rozszerzenia i odmiany (155)
- 4.1.1. Analiza przypadku średniego (155)
- 4.1.2. Algorytmy przybliżenia otoczki wypukłej (159)
- 4.1.3. Problem maksimów zbioru punktów (162)
- 4.1.4. Otoczka wypukła wielokąta prostego (170)
- 4.2. Zastosowania statystyczne (174)
- 4.2.1. Solidne oszacowania (175)
- 4.2.2. Regresja izotoniczna (177)
- 4.2.3. Klastrowanie (średnica zbioru punktów) (179)
- 4.3. Uwagi i komentarze (185)
- 4.4. Ćwiczenia (186)
- 5.1. Zbiór problemów (188)
- 5.2. Prototyp obliczeniowy: niepowtarzalność elementu (193)
- 5.3. Ograniczenia dolne (194)
- 5.4. Problem najbliższej pary: metoda "dziel i rządź" (196)
- 5.5. Rozwiązywanie lokalne problemów bliskości: diagram Voronoi (205)
- 5.5.1. Właściwości Voronoi (206)
- 5.5.2. Tworzenie diagramu Voronoi (212)
- 5.6. Rozwiązywanie problemów sąsiedztwa diagramem Voronoi (219)
- 5.7. Uwagi i komentarze (222)
- 5.8. Ćwiczenia (223)
- 6.1. Euklidesowe drzewa minimalne (225)
- 6.1.1. Problem komiwojażera w przestrzeni euklidesowej (228)
- 6.2. Triangulacje płaskie (232)
- 6.2.1. Triangulacja zachłanna (233)
- 6.2.2. Triangulacje ograniczone (235)
- 6.3. Uogólnienia diagramu Voronoi (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)
- 6.4. Przerwy i pokrycia (252)
- 6.5. Uwagi i komentarze (258)
- 6.6. Ćwiczenia (260)
- 7.1. Przykładowe zastosowania (264)
- 7.1.1. Problemy ukrytych linii i ukrytych powierzchni (264)
- 7.1.2. Rozpoznawanie wzorca (265)
- 7.1.3. Układ ścieżek i elementów (266)
- 7.1.4. Programowanie liniowe i wspólne przecięcie półprzestrzeni (267)
- 7.2. Zastosowania na płaszczyźnie (268)
- 7.2.1. Przecięcie wielokątów wypukłych (268)
- 7.2.2. Przecięcie wielokątów gwiazdokształtnych (273)
- 7.2.3. Przecięcie odcinków (274)
- 7.2.4. Przecięcie półpłaszczyzn (283)
- 7.2.5. Dwuzmienne programowanie liniowe (285)
- 7.2.6. Jądro wielokąta płaskiego (294)
- 7.3. Zastosowania trójwymiarowe (300)
- 7.3.1. Przecięcia wielościanów wypukłych (300)
- 7.3.2. Przecinanie półprzestrzeni (308)
- 7.4. Uwagi i komentarze (313)
- 7.5. Ćwiczenia (315)
- 8.1. Wybrane zastosowania geometrii prostokątów (317)
- 8.1.1. Wspomaganie projektowania VLSI (317)
- 8.1.2. Wielodostęp w bazach danych (319)
- 8.2. Dziedzina poprawności wyników (321)
- 8.3. Ogólne uwagi o algorytmach modelu statycznego (323)
- 8.4. Miara i obwód sumy prostokątów (325)
- 8.5. Kontur sumy prostokątów (332)
- 8.6. Domknięcie sumy prostokątów (339)
- 8.7. Zewnętrzny kontur sumy prostokątów (343)
- 8.8. Przecięcia prostokątów i podobne problemy (348)
- 8.8.1. Przecięcia prostokątów (348)
- 8.8.2. Jeszcze raz problem przecięcia prostokątów (352)
- 8.8.3. Zawieranie prostokątów (355)
- 8.9. Uwagi i komentarze (360)
- 8.10. Ćwiczenia (361)
Skorowidz (375)