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%)
• Lean dla bystrzaków. Wydanie II 49,62 zÅ‚, (12,90 zÅ‚ -74%)
• Gra bez koÅ„ca 47,78 zÅ‚, (12,90 zÅ‚ -73%)

• 
• 
• 
• 
• 

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)