Geometrie de calcul
Geometria computațională este ramura geometriei care studiază algoritmi eficienți pentru soluționarea problemelor de natură geometrică și implementarea lor pe computer .
Prin „algoritm eficient” înțelegem un algoritm care are o complexitate de calcul redusă, adică folosește cea mai mică cantitate posibilă de resurse în termeni de timp și spațiu de memorie ocupat în funcție de mărimea problemei.
Prin „algoritm exact” se înțelege un algoritm care, prin utilizarea unor tehnici specifice, evită operațiunile din punct de vedere computerizat, cu riscul de erori de rotunjire (în special diviziuni și funcții trigonometrice ).
Deși geometria computațională este o disciplină relativ recentă, folosește rezultate din multe alte domenii ale matematicii, cum ar fi algebra liniară , topologia și geometria combinatorie (în special teoria graficelor ).
Numele Computational Geometry a fost inventat de Marvin Minsky în cartea sa Perceptrons , dar a fost folosit pentru prima dată cu semnificația sa actuală în teza de doctorat Problems in Computational Geometry , scrisă de Ian Shamos în 1975.
Geometria computațională găsește aplicații importante în robotică , sisteme de informații geografice (GIS), grafică pe computer , logistică și CAD / CAM , doar pentru a numi câteva.
Exemple de probleme
Iată o listă a problemelor clasice care pot fi rezolvate cu tehnicile geometriei de calcul:
- Plic convex (carenă convexă): dat un set de puncte, determinați cel mai mic set convex care le conține pe toate.
- Intersecția segmentelor : determinați toate intersecțiile unui set dat de segmente.
- Diagramele Voronoi : având în vedere un set de puncte, determinați partiția planului în care fiecare clasă de echivalență conține un singur punct și este astfel încât toate punctele sale au o distanță mai mică de acel punct decât toate celelalte puncte atribuite.
- Triangulare : dat un poligon , determinați partiția acestuia în triunghiuri.
- Pereche de puncte cele mai apropiate (Cea mai apropiată pereche de puncte): având în vedere un set de puncte, determinați perechea de puncte care are o distanță mai mică între toate.
- Localizarea punctelor (locația punctului): având în vedere o partiție a planului (sau spațiului) și un punct, determinați clasa de echivalență care conține acel punct.
- Calea minimă ( calea cea mai scurtă euclidiană ): date două puncte pe plan și un set de obstacole poligonale, determinați calea cea mai scurtă poligonală care unește cele două puncte fără a intersecta obstacolele.
- Căutarea intervalului : având în vedere un set de puncte și o regiune a planului, analizați setul de puncte de date, pentru a conta eficient numărul de puncte din regiunea atribuită.
- În apropiere (cel mai apropiat vecin): dat un set de puncte și un alt punct, analizați setul dat pentru a determina în mod eficient care dintre ele are distanța minimă față de punctul atribuit.
- Triunghiurile Delaunay
- Programare liniară
Cărți
Iată o listă cu cele mai acreditate și citite cărți de geometrie de calcul:
- Franco P. Preparata și Michael Ian Shamos ,Computational Geometry - An Introduction , Springer-Verlag , 1985, prima ediție: ISBN 0-387-96131-3 ; A doua tipărire, corectată și extinsă, 1988: ISBN 3-540-96131-3 ; Traducere rusă, 1989: ISBN 5-03-001041-6 .
- Herbert Edelsbrunner , Algorithms in Combinatorial Geometry , Springer-Verlag , 1987, ISBN 0-89791-517-8 .
- Mark de Berg , Otfried Cheong , Marc van Kreveld și Mark Overmars , Computational Geometry , ediția a treia revizuită, Springer-Verlag , 2008, ISBN 3-540-77973-6 ,, ediția a 1-a (1987):.
- Jean-Daniel Boissonnat , Mariette Yvinec , Algorithmic Geometry , Traducerea unei ediții franceze din 1995, Cambridge University Press , 1998, ISBN 0-521-56529-4 .
- Kurt Mehlhorn , Structuri de date și algoritmi eficienți 3: căutare multidimensională și geometrie de calcul , Springer-Verlag , 1984.
- Ketan Mulmuley , Computational Geometry: An Introduction Through Randomized Algorithms , Prentice-Hall , 1994, ISBN 0-13-336363-5 .
- Joseph O'Rourke , Computational Geometry in C , ediția a II-a, Cambridge University Press , 1998, ISBN 0-521-64976-5 .
- Janos Pach și Pankaj K. Agarwal ,Geometrie combinatorie , John Wiley și Sons , 1995, ISBN 0-471-58890-3 .
- Micha Sharir și Pankaj K. Agarwal , Davenport - Schinzel Sequences and Their Geometric Applications , Cambridge University Press , 1995, ISBN 0-521-47025-0 .
- Kurt Mehlhorn și Stefan Naeher , LEDA, A Platform for Combinatorial and Geometric Computing , Cambridge University Press , 1999, ISBN 0-521-56329-1 .
- Jörg-Rüdiger Sack și Jorge Urrutia , Handbook for Computational Geometry , North-Holland , 1998, prima ediție: ISBN 0-444-82537-1 , a 2-a ediție: 1-584-88301-4.
- Selim G. Akl și Kelly A. Lyons , Parallel Computational Geometry , Prentice-Hall , 1993, ISBN 0-13-652017-0 .
- Clara I. Grima și Alberto Márquez, Computational Geometry on Surfaces: Performing Computational Geometry on the Cylinder, the Sphere, the Torus, and the Cone , Kluwer Academic Publishers , 1990, ISBN 1-4020-0202-5 .
- Subir Kumar Ghosh, Algoritmi de vizibilitate în plan , Cambridge University Press , 2007, ISBN 0-521-87574-9 .
- Giri Narasimhan, Michiel Smid, Geometric Spanner Networks , Cambridge University Press , 2007, ISBN 0-521-81513-4 .
- Jacob E. Goodman și Joseph O'Rourke (editori), Handbook for Computational Geometry , North-Holland , 1997, 2004, prima ediție: ISBN 0-8493-8524-5 , a doua ediție: ISBN 1-584-88301-4 .
- JR Sack și J. Urrutia (eds.), Handbook of Computational Geometry , North Holland , 2000, ISBN 0-444-82537-1 .
Reviste
Iată o listă a principalelor reviste internaționale care publică articole de cercetare în geometrie de calcul. Trebuie remarcat faptul că odată cu creșterea revistelor dedicate în mod special acestui sector, publicațiile din reviste mai generice (informatică teoretică și grafică pe computer) au scăzut semnificativ.
- Sondaje de calcul ACM
- Tranzacții ACM pe grafică
- Acta Informatica
- Progrese în geometrie
- Jurnal internațional de geometrie diferențială (www.ijournaldg.cc.cc)
- Algorithmica
- Ars Combinatoria
- Geometrie computațională: teorie și aplicații
- Comunicări ale ACM
- Proiectare geometrică asistată de computer
- Calculatoare și aplicații
- Computer Graphics World
- Geometrie discretă și computațională
- Geombinatorie
- Geometrie dedicată
- Tranzacții IEEE pe grafică
- Tranzacții IEEE pe computere
- Tranzacții IEEE privind analiza modelelor și inteligența mașinilor
- Scrisori de prelucrare a informațiilor
- Jurnalul Internațional de Geometrie și Aplicații Computaționale
- Journal of Combinatorial Theory , seria B
- Jurnalul ACM
- Journal of Algorithms
- Journal of Computer and System Sciences
- Știința managementului
- Recunoasterea formelor
- Scrisori de recunoaștere a modelelor
- SIAM Journal on Computing
- Știri SIGACT ; a prezentat „Coloana Computational Geometry” de Joseph O'Rourke
- Informatică teoretică
- Calculatorul vizual
linkuri externe
- Computational Geometry , la computational-geometry.org .
- Pagini Computational Geometry , la compgeom.cs.uiuc.edu . Adus pe 2 martie 2010 (arhivat din original la 6 noiembrie 2011) .
- Geometry In Action , la ics.uci.edu .
- „Direcții strategice în geometria calculațională - raportul grupului de lucru” (1996) , pe cs.brown.edu .
Controlul autorității | GND ( DE ) 4130267-9 |
---|