Geometria obliczeniowa Wprowadzenie.pdf
(
569 KB
)
Pobierz
C:\Andrzej\PDF\ABC nagrywania p³yt CD\1 strona.cdr
IDZ DO
PRZYK£ADOW
Y ROZDZIA£
Geometria obliczeniowa.
SPIS TRECI
Wprowadzenie
KATALOG KSI¥¯EK
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
KATALOG ONLINE
ZAMÓW DRUKOWANY KATALOG
TWÓJ KOSZYK
DODAJ DO KOSZYKA
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³aciwoci
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¹.
CENNIK I INFORMACJE
ZAMÓW INFORMACJE
O NOWOCIACH
ZAMÓW CENNIK
CZYTELNIA
FRAGMENTY KSI¥¯EK ONLINE
Wydawnictwo Helion
ul. Chopina 6
44-100 Gliwice
tel. (32)230-98-63
e-mail: helion@helion.pl
Spis treci
Wstp do wydania drugiego...............................................................................9
Wstp ....................................................................................................................11
1
Wprowadzenie ....................................................................................................13
1.1. Rys historyczny..........................................................................................................................13
1.1.1. Złoono geometrii klasycznej........................................................................................14
1.1.2. Teoria zbiorów wypukłych, geometria metryczna i kombinatoryczna............................16
1.1.3. Wczeniejsze prace ...........................................................................................................16
1.1.4. Ku geometrii obliczeniowej ..............................................................................................17
1.2. Wprowadzenie do algorytmów .................................................................................................17
1.2.1. Algorytmy: zapis i okrelanie wydajnoci........................................................................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, przyj2te konwencje................................................................................28
1.3.2. Niezmienniki grup przekształce3 liniowych....................................................................30
1.3.3. Dualno geometryczna. Biegunowo ............................................................................35
1.4. Modele obliczeniowe..................................................................................................................37
Przeszukiwanie geometryczne..........................................................................47
2.1. Wprowadzenie do przeszukiwania geometrycznego................................................................47
2.2. Problemy lokalizacji punktu ......................................................................................................51
2.2.1. Rozwaania ogólne. Najprostsze przypadki ....................................................................51
2.2.2. Lokalizacja punktu w obszarze płaszczyzny....................................................................55
2.3. Problemy zwi9zane z przeszukiwaniem zakresu......................................................................78
2.3.1. Rozwaania ogólne...........................................................................................................78
2.3.2. Metoda wielowymiarowego drzewa binarnego (k-D drzewa).........................................83
2.3.3. Metoda bezporedniego dost2pu i jej odmiany................................................................87
2.3.4. Metoda drzew zakresu i jej odmiany................................................................................91
6
SPIS TRECI
2.4. Szukanie iterowane i kaskadowanie ułamkowe........................................................................96
2.5. Uwagi i komentarze...................................................................................................................99
2.6. ?wiczenia.................................................................................................................................101
Otoczki wypukłe: algorytmy podstawowe...................................................103
3.1. Informacje wst2pne..................................................................................................................103
3.2. Sformułowanie problemu i ograniczenia dolne.......................................................................107
3.3. Algorytmy otoczki wypukłej na płaszczyAnie .........................................................................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 rz9dA”......................................................................................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 wi2kszej 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
Otoczki wypukłe: rozszerzenia i zastosowanie ...........................................155
4.1. Rozszerzenia i odmiany ...........................................................................................................155
4.1.1. Analiza przypadku redniego ........................................................................................155
4.1.2. Algorytmy przyblienia otoczki wypukłej.....................................................................159
4.1.3. Problem maksimów zbioru punktów.............................................................................162
4.1.4. Otoczka wypukła wielok9ta 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
Blisko$%: algorytmy podstawowe...................................................................187
5.1. Zbiór problemów .....................................................................................................................188
5.2. Prototyp obliczeniowy: niepowtarzalno elementu ...............................................................193
5.3. Ograniczenia dolne...................................................................................................................194
5.4. Problem najbliszej pary: metoda „dziel i rz9dA”......................................................................196
5.5. Rozwi9zywanie lokalne problemów bliskoci: diagram Voronoi............................................205
5.5.1. Właciwoci Voronoi ......................................................................................................206
5.5.2. Tworzenie diagramu Voronoi.........................................................................................212
SPIS TRECI
7
5.6. Rozwi9zywanie problemów s9siedztwa diagramem Voronoi.................................................219
5.7. Uwagi i komentarze.................................................................................................................222
5.8. ?wiczenia.................................................................................................................................223
Blisko$%: odmiany i uogólnienia.....................................................................225
6.1. Euklidesowe drzewa minimalne..............................................................................................225
6.1.1. Problem komiwojaera 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 wyszego rz2du (na płaszczyAnie)..................................................239
6.3.2. Wielowymiarowe diagramy Voronoi punktu najbliszego i punktu najdalszego.........249
6.4. Przerwy i pokrycia...................................................................................................................252
6.5. Uwagi i komentarze.................................................................................................................258
6.6. ?wiczenia.................................................................................................................................260
Przecicia............................................................................................................263
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 cieek i elementów.............................................................................................266
7.1.4. Programowanie liniowe i wspólne przeci2cie półprzestrzeni........................................267
7.2. Zastosowania na płaszczyAnie .................................................................................................268
7.2.1. Przeci2cie wielok9tów wypukłych..................................................................................268
7.2.2. Przeci2cie wielok9tów gwiazdokształtnych....................................................................273
7.2.3. Przeci2cie odcinków .......................................................................................................274
7.2.4. Przeci2cie półpłaszczyzn.................................................................................................283
7.2.5. Dwuzmienne programowanie liniowe...........................................................................285
7.2.6. J9dro wielok9ta płaskiego...............................................................................................294
7.3. Zastosowania trójwymiarowe..................................................................................................300
7.3.1. Przeci2cia wielocianów wypukłych ..............................................................................300
7.3.2. Przecinanie półprzestrzeni..............................................................................................308
7.4. Uwagi i komentarze.................................................................................................................313
7.5. ?wiczenia.................................................................................................................................315
Geometria prostok+tów....................................................................................317
8.1. Wybrane zastosowania geometrii prostok9tów.......................................................................317
8.1.1. Wspomaganie projektowania VLSI.................................................................................317
8.1.2. Wielodost2p w bazach danych .......................................................................................319
8.2. Dziedzina poprawnoci wyników............................................................................................321
8.3. Ogólne uwagi o algorytmach modelu statycznego..................................................................323
8
SPIS TRECI
8.4. Miara i obwód sumy prostok9tów...........................................................................................325
8.5. Kontur sumy prostok9tów.......................................................................................................332
8.6. Domkni2cie sumy prostok9tów ...............................................................................................339
8.7. Zewn2trzny kontur sumy prostok9tów...................................................................................343
8.8. Przeci2cia prostok9tów i podobne problemy...........................................................................348
8.8.1. Przeci2cia prostok9tów...................................................................................................348
8.8.2. Jeszcze raz problem przeci2cia prostok9tów..................................................................352
8.8.3. Zawieranie prostok9tów.................................................................................................355
8.9. Uwagi i komentarze.................................................................................................................360
8.10. ?wiczenia...............................................................................................................................361
Literatura ............................................................................................................363
Skorowidz...................... ....................................................................................375
Plik z chomika:
Ravel25
Inne pliki z tego folderu:
Asembler dla procesorow Intel Vademecum profesjonalisty.pdf
(400 KB)
Asembler cwiczenia praktyczne.pdf
(358 KB)
Architektura systemow zarzadzania przedsiebiorstwem Wzorce projektowe.pdf
(829 KB)
Architektura oprogramowania Metody oceny oraz analiza przypadkow.pdf
(429 KB)
Aplikacje w Visual C++ 2005 Przyklady.pdf
(296 KB)
Inne foldery tego chomika:
(X) HTML
algorytmy i struktury danych
asembler
C++
Core JAVA2 Podstawy
Zgłoś jeśli
naruszono regulamin