Jest to podręcznik do
geometrii obliczeniowej – dziedziny informatyki bardzo prężnie się rozwijającej.
Autorzy omawiają m.in. otoczkę wypukłą, przecięcia odcinków, geometryczne struktury
danych, diagramy Yoronoi, lokalizację punktu, problem galerii, programowanie liniowe,
planowanie przesunięć obiektów, przekształcenia dualne i algorytmy randomizacyjne.
Każdy rozdział kończą
uwagami rozszerzającymi wiedzę Czytelnika oraz licznymi ćwiczeniami. Zamieszczają też
wiele rysunków, które ułatwiają zrozumienie poruszanych zagadnień.
Na polskim rynku brakuje
pozycji na ten temat, a jest ona bardzo potrzebna studentom informatyki na wszystkich
uczelniach wyższych. Fakt, że wszystkie rozwiązania i techniki pochodzące z geometrii
obliczeniowej odnoszą się do określonych zastosowań w robotyce, grafice, systemach
CAD/CAM i systemach informacji geograficznej, powinien zachęcić ich do zgłębiania tego
przedmiotu.
Spis treści:
l.
Geometria
obliczeniowa
Wstęp
1.1 Przykład: otoczka
wypukła
l .2 Degeneracje i odporność
na błędy
1.3 Dziedziny zastosowań
1.4 Uwagi i komentarze
l .5 Zadania
2.
Przecinanie się odcinków Nakładanie map tematycznych
2.l. Przecinanie się
odcinków
2.2. Podwójnie łączona lista
krawędzi
2.3. Obliczanie nałożenia dwóch
podziałów
2.4. Operacje boolowskie
2.5. Uwagi i komentarze
2.6. Zadania
3.
Triangulacja wielokąta. Ochrona galerii sztuki
3. L. Ochrona i triangulacje
3.2. Podział wielokąta na części
monotoniczne
3.3. Triangulacja wielokątów
monotonicznych
3.4. Uwagi i komentarze
3.5. Zadania
4.
Programowanie liniowe Produkcja z użyciem form odlewniczych
4.1. Geometria odlewania
4.2. Przecięcie półpłaszczyzn
4.3. Przyrostowe programowanie
liniowe
4.4. Randomizowane programowanie
liniowe
4.5. Nieograniczone programowanie
liniowe
4.6. Programowanie liniowe w
wyższych wymiarach
4.7. Najmniejsze koło zawierające
5.
Przeszukiwanie obszarów ortogonalnych Zadawanie pytań bazie danych
5.1. Przeszukiwanie obszarów
jednowymiarowych
5.2. Kd-drzewa
5.3. Drzewa obszarów
5.4. Wielowymiarowe drzewa obszarów
5.5. Ogólny zbiór punktów
5.6. Kaskadowanie cząstkowe
5.7. Uwagi i komentarze
5.8. Zadania
6.
Lokalizacja punktu. Wiedza o tym, gdzie się znajdujemy
6.1. Lokalizacja punktu w mapach
trapezowych
6.2. Randomizowany algorytm
przyrostowy
6.3. Postępowanie z przypadkami
zdegenerowanymi
6.4. Oszacowanie dolne
6.5. Uwagi i komentarze
6.6. Zadania
7.
Diagramy Yoronoi. Problem urzędu pocztowego
7.1. Definicja i podstawowe
własności
7.2. Obliczanie diagramu Yoronoi
7.3. Uwagi i komentarze
7.4. Zadania
8. Układy
i dualność. Superpróbkowanie w śledzeniu promieni
8.1 Obliczanie niezgodności
8.2 Dualność
8.3 Układy prostych
8.4 Poziomy i niezgodność
8.5 Uwagi i komentarze
8.6 Zadania
9.
Triangulacje Delaunaya. Interpolacja wysokości
9.1. Triangulacje planarnych
zbiorów punktów
9.2. Triangulacja Delaunaya
9.3. Obliczanie triangulacji
Delaunaya
9.4. Analiza
9.5. Schemat algorytmów
randomizowanych
9.6. Uwagi i komentarze
9.7. Zadania
10. Więcej
geometrycznych struktur danych. Okienkowanie
10.l. Drzewa przedziałów
10.2. Drzewa przeszukiwań priorytetowych
10.3. Drzewa odcinków
10.4. Uwagi i komentarze
10.5. Zadania
11. Otoczka wypukła.
Pomieszanie sprawy
11.1. Złożoność otoczki wypukłej w
przestrzeni trójwymiarowej
11.2. Obliczanie otoczki wypukłej w przestrzeni
trójwymiarowej
11.3. Analiza
11.4. Otoczki wypukłe i przecięcie
półprzestrzeni
11.5. Diagram Yoronoi raz jeszcze
11.6. Uwagi i komentarze
11.7. Zadania
12. Binarne podziały
przestrzeni. Algorytm malarza
12.1. Definicja drzew BSP
12.2. Drzewa BSP i algorytm malarza
12.3. Konstrukcja drzew BSP
12.4. Rozmiar drzew BSP w przestrzeni
trójwymiarowej
12.5. Uwagi i komentarze
12.6. Zadania
13. Planowanie ruchu
robota. Docieranie tam, gdzie chcemy być
13.1. Przestrzeń robocza i przestrzeń
konfiguracyjna
13.2. Robot punktowy
13.3. Sumy Minkowskiego
13.4. Planowanie ruchu postępowego
13.5. Planowanie ruchu z obrotami
13.6. Uwagi i komentarze
13.7. Zadania
14. Drzewa ćwiartek.
Tworzenie niejednolitych siatek
14.1. Siatki jednolite i niejednolite
14.2. Drzewa ćwiartek dla zbiorów punktów
14.3. Od drzew ćwiartek do siatek
14.4. Uwagi i komentarze
14.5. Zadania
15. Grafy
widzialności. Znajdywanie najkrótszej drogi
15.1. Najkrótsza ścieżka dla robota
punktowego
15.2. Obliczanie grafu widzialności
15.3. Najkrótsze ścieżki dla robota
wielokątnego poruszającego się ruchem postępowym
15.4. Uwagi i komentarze
15.5. Zadania
16. Przeszukiwanie
obszarów sympleksowych Okienkowanie jeszcze raz
16.1.
Drzewa podziałów
16.2. Wielopoziomowe drzewa podziałów
16.3. Drzewa cięć
16.4. Uwagi i komentarze
16.5. Zadania
Bibliografia
Skorowidz
432 strony, oprawa twarda
-