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ą.

 

Osoby które kupowały "Geometria obliczeniowa. Wprowadzenie ", wybierały także:

• Windows Media Center. Domowe centrum rozrywki 66,67 zł, (8,00 zł -88%)
• Przywództwo w świecie VUCA. Jak być skutecznym liderem w niepewnym środowisku 58,64 zł, (12,90 zł -78%)
• Mapa Agile & Scrum. Jak si 57,69 zł, (15,00 zł -74%)
• Sztuka podst 53,46 zł, (13,90 zł -74%)
• Lean dla bystrzaków. Wydanie II 49,62 zł, (12,90 zł -74%)

• 
• 
• 
• 
• 

Spis treści

Geometria obliczeniowa. Wprowadzenie -- spis treści

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. Przeszukiwanie geometryczne (47)

• 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. Otoczki wypukłe: algorytmy podstawowe (103)

• 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. Otoczki wypukłe: rozszerzenia i zastosowanie (155)

• 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. 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 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. Bliskość: odmiany i uogólnienia (225)

• 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. Przecięcia (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 ś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. Geometria prostokątów (317)

• 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)

Literatura (363)

Skorowidz (375)