Seznam knih ve výpočetní geometrii - List of books in computational geometry

Tohle je seznam knih v výpočetní geometrie.Existují dvě hlavní, převážně nepřekrývající se kategorie:

  • Používá se kombinatorická výpočetní geometrie, která se zabývá sbírkami diskrétních objektů nebo je definována diskrétními pojmy: body, úsečky, polygony, polytopy atd. A používají se algoritmy diskrétního / kombinatorického charakteru.
  • Numerická výpočetní geometrie, známá také jako geometrické modelování a počítačem podporovaný geometrický design (CAGD), která se zabývá modelováním tvarů reálných objektů z hlediska křivek a ploch s algebraickou reprezentací.

Kombinatorická výpočetní geometrie

Univerzální učebnice

  • Franco P. Preparata a Michael Ian Shamos (1985). Výpočetní geometrie - úvod. Springer-Verlag. 1. vydání: ISBN  0-387-96131-3; 2. tisk, opraveno a rozšířeno, 1988: ISBN  3-540-96131-3; Ruský překlad, 1989: ISBN  5-03-001041-6.CS1 maint: používá parametr autoři (odkaz)
    Kniha je první komplexní monografií na úrovni absolventské učebnice, která systematicky pokrývá základní aspekty rozvíjející se disciplíny výpočetní geometrie. Je napsán zakladateli oboru a první vydání se týkalo všech hlavních vývojových trendů za posledních 10 let. Z hlediska komplexnosti tomu předcházela pouze studie z roku 1984, Lee, D, T., Preparata, F. P.: „Computational Geometry - a survey“. IEEE Trans. na počítačích. Sv. 33, č. 12, str. 1072–1101 (1984). Je zaměřen na dvourozměrné problémy, ale má také odbočení do vyšších dimenzí.[1][2]
    Prvotním jádrem knihy byla disertační práce M.I.Shamose, kterou navrhl proměnit v knihu ještě další průkopník v oboru, Ronald Graham.
    Úvod se věnuje historii oboru, základním datovým strukturám a nezbytným pojmům z EU teorie výpočtu a geometrie.
    Následující části pokrývají geometrické vyhledávání (umístění bodu, vyhledávání rozsahu ), konvexní obal výpočet, problémy související s blízkostí (nejbližší body, výpočet a aplikace Voronoiho diagram, Euklidovský minimální kostra, triangulace, atd.), problémy s geometrickými průniky, algoritmy pro množiny izotetické obdélníky
  • Herbert Edelsbrunner (1987). Algoritmy v kombinatorické geometrii. Springer-Verlag. ISBN  0-89791-517-8.
    Monografie je poměrně pokročilou expozicí problémů a přístupů ve výpočetní geometrii se zaměřením na roli uspořádání nadroviny, u nichž je prokázáno, že tvoří základní podkladovou kombinatoricko-geometrickou strukturu v určitých oblastech pole. Primárním cílovým publikem jsou spíše aktivní teoretičtí vědci v oboru než vývojáři aplikací. Na rozdíl od většiny knih ve výpočetní geometrii zaměřených na 2- a 3-dimenzionální problémy (kde je většina aplikací výpočetní geometrie), má kniha za cíl zacházet s jejím předmětem v obecném vícerozměrném prostředí.[3]
  • Mark de Berg, Otfried Cheong, Marc van Kreveld, a Mark Overmars (2008). Výpočetní geometrie (3. přepracované vydání). Springer-Verlag. ISBN  3-540-77973-6. 1. vydání (1997): ISBN  3-540-61270-X.CS1 maint: používá parametr autoři (odkaz)
    Učebnice poskytuje úvod do výpočetní geometrie z hlediska praktických aplikací. Počínaje úvodní kapitolou každý z 15 zbývajících formuluje skutečný aplikační problém, formuluje základní geometrický problém a diskutuje techniky výpočetní geometrie užitečné pro jeho řešení, s algoritmy poskytnutými v pseudokódu. Kniha pojednává převážně o 2- a 3-dimenzionální geometrii. Cílem knihy je poskytnout komplexní úvod do metod a přiblížených metod, nikoli špičku výzkumu v této oblasti: předložené algoritmy poskytují transparentní a přiměřeně efektivní řešení založená na základních „stavebních blocích“ výpočetní geometrie.[4][5]
    Kniha se skládá z následujících kapitol (které poskytují jak řešení tématu názvu, tak jeho aplikací): „Výpočetní geometrie (úvod)“ „Průsečík segmentů čáry“, „Polygonová trojúhelníkování“, „Lineární programování“, „Hledání ortogonálního rozsahu "," Bodové umístění "," Voronoiovy diagramy "," Uspořádání a dualita "," Delaunayovy trojúhelníky "," Více geometrických datových struktur "," Konvexní trupy "," Binární prostorové oddíly "," Plánování pohybu robota "," Čtyřstěny " , "Grafy viditelnosti", "Hledání jednoduchého rozsahu".
  • Jean-Daniel Boissonnat, Mariette Yvinec (1998). Algoritmická geometrie. Cambridge University Press. ISBN  0-521-56529-4. Překlad francouzského vydání z roku 1995.CS1 maint: používá parametr autoři (odkaz)
  • Joseph O'Rourke (1998). Výpočetní geometrie v jazyce C. (2. vyd.). Cambridge University Press. ISBN  0-521-64976-5.
  • Satyan Devadoss, Joseph O'Rourke (2011). Diskrétní a výpočetní geometrie. Princeton University Press. ISBN  978-0-691-14553-2.CS1 maint: používá parametr autoři (odkaz)
  • Jim Arlow (2014). Interaktivní výpočetní geometrie - taxonomický přístup. Mountain Way Limited. 1. vydání: ISBN  978-0-9572928-2-6.
    Tato kniha je interaktivním úvodem do základních algoritmů výpočetní geometrie, formátovaných jako interaktivní dokument zobrazitelný pomocí softwaru založeného na Mathematica.

Odborné učebnice a monografie

Reference

  • Jacob E. Goodman; Joseph O'Rourke, eds. (2004) [1997]. Příručka diskrétní a výpočetní geometrie. Severní Holandsko. 1. vydání: ISBN  0-8493-8524-5, 2. vydání: ISBN  1-58488-301-4.
    Ve své organizaci se kniha podobá klasické příručce v algoritmech, Úvod do algoritmů ve své komplexnosti omezen pouze na diskrétní a výpočetní geometrii, výpočetní topologie, jakož i širokou škálu jejich aplikací. Druhé vydání rozšiřuje knihu o polovinu, je přidáno 14 kapitol a aktualizovány staré kapitoly. Jeho 65 kapitol (na více než 1 500 stranách) je napsáno velkým týmem aktivních výzkumníků v oboru.[6]
  • Jörg-Rudiger Sack; Jorge Urrutia (1998). Příručka výpočetní geometrie. Severní Holandsko. 1. vydání: ISBN  0-444-82537-1, 2. vydání (2000): 1-584-88301-4.
    Příručka obsahuje kapitoly průzkumu v klasických i nových studiích geometrických algoritmů: uspořádání nadrovin, Voronoiovy diagramy, geometrické a prostorové datové struktury, rozklad polygonů, randomizované algoritmy, derandomizace, paralelní výpočetní geometrie (deterministická a randomizovaná), viditelnost, galerie umění a problémy osvětlení , problémy s nejbližším bodem, vzdálenost odkazu problémy, podobnost geometrických objektů, Sekvence Davenport – Schinzel, klenout se nad stromy a klíče pro geometrické grafy, robustnost a numerické problémy pro geometrické algoritmy, animace a kreslení grafů.
    Kniha navíc mapuje aplikace geometrických algoritmů v oblastech, jako je geografické informační systémy, geometrická nejkratší cesta a optimalizace sítě a generování sítě.
  • Ding-Zhu Du; Frank Hwang (1995). Výpočet v euklidovské geometrii. Přednášky Notes Series on Computing. 4 (2. vyd.). World Scientific. ISBN  981-02-1876-1.
    „Tato kniha je souborem průzkumů a průzkumných článků o nedávném vývoji v oblasti výpočetní euklidovské geometrie.“[7] Jeho 11 kapitol zahrnuje kvantitativní geometrii, historii výpočetní geometrie, generování sítí, automatické generování geometrických důkazů, randomizované geometrické algoritmy, problémy Steinerova stromu, Voronoiho diagramy a Delaunayovy triangulace, řešení omezení, spline plochy, návrh sítě a numerická primitiva pro geometrii výpočetní.

Numerická výpočetní geometrie (geometrické modelování, počítačově podporovaný geometrický design)

Monografie

jiný

Konference

Níže uvedené konference, širokého rozsahu, publikovaly mnoho klíčových prací v této oblasti.

Papírové sbírky

  • „Combinatorial and Computational Geometry“, eds. Jacob E. Goodman, János Pach, Emo Welzl (MSRI Publikace - svazek 52), 2005, ISBN  0-521-84862-8.
    • 32 příspěvků, včetně průzkumů a výzkumných článků o geometrických uspořádáních, polytopech, balení, krytí, diskrétní konvexitě, geometrických algoritmech a jejich výpočetní složitosti a kombinatorické složitosti geometrických objektů.
  • „Průzkumy diskrétní a výpočetní geometrie: o dvacet let později“ (seriál „Současná matematika“), Americká matematická společnost, 2008, ISBN  0-8218-4239-0

Viz také

Reference

  1. ^ PAN0805539, PAN1004870
  2. ^ Zbl  0575.68037, Zbl  0575.68059
  3. ^ Recenze Edelsbrunnerovy knihy v Zbl  0634.52001
  4. ^ Recenze v Zbl  0877.68001 (1. vyd.), Zbl  0939.68134 (2. vyd.)
  5. ^ O knize od de Berga, van Krevelda, Overmarse a Schwarzkopfa
  6. ^ Přezkum Příručka pro výpočetní geometrii v Geombinatorika, Leden 2005.
  7. ^ Z flyleaf knihy.

externí odkazy