Geometrie de calcul

De la Wikipedia, enciclopedia liberă.
Salt la navigare Salt la căutare

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:

  • Kurt Mehlhorn , Structuri de date și algoritmi eficienți 3: căutare multidimensională și geometrie de calcul , Springer-Verlag , 1984.
  • 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 .

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.

linkuri externe

Controlul autorității GND ( DE ) 4130267-9