Geometria obliczeniowa - Computational geometry

Dla czasopisma zobacz Geometria obliczeniowa (czasopismo) .

Geometria obliczeniowa to dział informatyki poświęcony badaniu algorytmów, które można określić w kategoriach geometrii . Niektóre problemy czysto geometryczne wynikają z badania algorytmów geometrycznych obliczeniowych i takie problemy są również uważane za część geometrii obliczeniowej. Chociaż współczesna geometria obliczeniowa jest najnowszym osiągnięciem, jest to jedna z najstarszych dziedzin informatyki, której historia sięga starożytności.

Złożoność obliczeniowa ma kluczowe znaczenie dla geometrii obliczeniowej, co ma ogromne znaczenie praktyczne, jeśli algorytmy są używane na bardzo dużych zbiorach danych zawierających dziesiątki lub setki milionów punktów. Do takich zbiorów, różnica pomiędzy O ( n- 2 ) i O ( n log n ) może być różnica między dniami i sekundach obliczeń.

Głównym impulsem do rozwoju geometrii obliczeniowej jako dyscypliny był postęp w grafice komputerowej oraz komputerowym wspomaganiu projektowania i wytwarzania ( CAD / CAM ), ale wiele problemów w geometrii obliczeniowej ma charakter klasyczny i może pochodzić z wizualizacji matematycznej .

Inne ważne zastosowania geometrii obliczeniowej obejmują robotykę ( planowanie ruchu i problemy widoczność), systemów informacji geograficznej (GIS) (geometrycznego położenia oraz wyszukiwanie, planowanie trasy), układ scalony projektowe (IC projektowania geometrii i weryfikacji), inżynierii wspomaganej komputerowo (CAE) (generowanie siatek) oraz widzenie komputerowe ( rekonstrukcja 3D ).

Główne gałęzie geometrii obliczeniowej to:

  • Kombinatoryczna geometria obliczeniowa , zwana również geometrią algorytmiczną , która zajmuje się obiektami geometrycznymi jako jednostkami dyskretnymi . Podstawowa książka na ten temat autorstwa Preparata i Shamos datuje pierwsze użycie terminu „geometria obliczeniowa” w tym znaczeniu w 1975 roku.
  • Numeryczna geometria obliczeniowa , zwana także geometrią maszynową , komputerowym wspomaganiem projektowania geometrycznego (CAGD) lub modelowaniem geometrycznym , które zajmuje się przede wszystkim przedstawianiem obiektów ze świata rzeczywistego w formach odpowiednich do obliczeń komputerowych w systemach CAD/CAM. Ta gałąź może być postrzegana jako dalszy rozwój geometrii wykreślnej i często jest uważana za gałąź grafiki komputerowej lub CAD. Termin „geometria obliczeniowa” w tym znaczeniu jest używany od 1971 roku.

Chociaż większość algorytmów geometrii obliczeniowej została opracowana (i jest rozwijana) dla komputerów elektronicznych, niektóre algorytmy zostały opracowane dla komputerów niekonwencjonalnych (np. komputerów optycznych).

Kombinatoryczna geometria obliczeniowa

Podstawowym celem badań w kombinatorycznej geometrii obliczeniowej jest opracowanie wydajnych algorytmów i struktur danych do rozwiązywania problemów postawionych w zakresie podstawowych obiektów geometrycznych: punktów, odcinków linii, wielokątów , wielościanów itp.

Niektóre z tych problemów wydają się tak proste, że nie uważano ich za problemy aż do pojawienia się komputerów . Rozważmy na przykład problem z najbliższą parą :

  • Mając n punktów na płaszczyźnie, znajdź dwa znajdujące się w najmniejszej odległości od siebie.

Można by obliczyć odległości pomiędzy wszystkimi parami punktów, których jest n(n-1)/2 , a następnie wybrać parę o najmniejszej odległości. Ten algorytm brutalnej siły zajmuje O ( n 2 ) czasu; tzn. czas jego wykonania jest proporcjonalny do kwadratu liczby punktów. Klasycznym wynikiem geometrii obliczeniowej było sformułowanie algorytmu, który przyjmuje O( n log n ). Odkryto również algorytmy randomizowane, które zajmują O( n ) oczekiwany czas, a także algorytm deterministyczny, który zajmuje O( n log log n ) czasu.

Klasy problemowe

Podstawowe problemy geometrii obliczeniowej można klasyfikować na różne sposoby, według różnych kryteriów. Można wyróżnić następujące klasy ogólne.

Problemy statyczne

W problemach tej kategorii podaje się pewne dane wejściowe, a odpowiadające im dane wyjściowe muszą być skonstruowane lub znalezione. Niektóre podstawowe problemy tego typu to:

Złożoność obliczeniowa dla tej klasy problemów jest szacowana przez czas i przestrzeń (pamięć komputera) wymaganą do rozwiązania danej instancji problemu.

Problemy z zapytaniami geometrycznymi

W geometrycznych problemach zapytań, powszechnie znanych jako geometryczne problemy wyszukiwania, dane wejściowe składają się z dwóch części: części przestrzeni poszukiwań i części zapytania , która zmienia się w zależności od instancji problemu. Przestrzeń wyszukiwania zazwyczaj wymaga wstępnego przetworzenia , aby można było skutecznie odpowiedzieć na wiele zapytań.

Niektóre podstawowe problemy z zapytaniami geometrycznymi to:

  • Wyszukiwanie w zakresie : Przetwarzaj wstępnie zestaw punktów, aby skutecznie policzyć liczbę punktów w obszarze zapytania.
  • Lokalizacja punktu : biorąc pod uwagę podział przestrzeni na komórki, utwórz strukturę danych, która skutecznie informuje, w której komórce znajduje się punkt zapytania.
  • Najbliższy sąsiad : Wstępnie przetwórz zestaw punktów, aby skutecznie znaleźć, który punkt jest najbliżej punktu zapytania.
  • Śledzenie promieni : Mając zestaw obiektów w przestrzeni, utwórz strukturę danych, która skutecznie informuje, który obiekt przecina promień zapytania jako pierwszy.

Jeśli przestrzeń poszukiwań jest stała, złożoność obliczeniowa dla tej klasy problemów jest zwykle szacowana przez:

  • czas i miejsce potrzebne do zbudowania struktury danych do przeszukania
  • czas (a czasem dodatkowe miejsce) na udzielenie odpowiedzi na pytania.

W przypadku, gdy przestrzeń wyszukiwania może się zmieniać, zobacz " Problemy dynamiczne ".

Problemy dynamiczne

Jeszcze inną ważną klasą są problemy dynamiczne , w których celem jest znalezienie wydajnego algorytmu do wielokrotnego znajdowania rozwiązania po każdej przyrostowej modyfikacji danych wejściowych (dodawanie lub usuwanie wejściowych elementów geometrycznych). Algorytmy rozwiązywania tego typu problemów zazwyczaj obejmują dynamiczne struktury danych . Każdy z obliczeniowych problemów geometrycznych można przekształcić w dynamiczny, kosztem zwiększonego czasu przetwarzania. Na przykład, problem przeszukiwania zakresu może zostać przekształcony w problem przeszukiwania zakresu dynamicznego przez dodanie i/lub usunięcie punktów. Problem dynamicznej kadłuba wypukłego polega na śledzeniu kadłuba wypukłego, np. dla dynamicznie zmieniającego się zbioru punktów, tj. podczas wstawiania lub usuwania punktów wejściowych.

Złożoność obliczeniowa dla tej klasy problemów jest szacowana przez:

  • czas i miejsce potrzebne do zbudowania struktury danych do przeszukania
  • czas i przestrzeń na modyfikację przeszukiwanej struktury danych po stopniowej zmianie w przestrzeni wyszukiwania
  • czas (a czasem dodatkowa spacja) na udzielenie odpowiedzi na zapytanie.

Wariacje

Niektóre problemy, w zależności od kontekstu, mogą być traktowane jako należące do jednej z kategorii. Rozważmy na przykład następujący problem.

  • Punkt w wielokącie : zdecyduj, czy punkt znajduje się wewnątrz, czy na zewnątrz danego wielokąta.

W wielu zastosowaniach problem ten traktowany jest jako jednorazowy, czyli przynależny do pierwszej klasy. Na przykład w wielu zastosowaniach grafiki komputerowej powszechnym problemem jest odnalezienie obszaru ekranu, który jest klikany wskaźnikiem . Jednak w niektórych aplikacjach dany wielokąt jest niezmienny, a punkt reprezentuje zapytanie. Na przykład wielokąt wejściowy może reprezentować granicę państwa, a punkt to pozycja samolotu, a problem polega na ustaleniu, czy samolot naruszył granicę. Wreszcie, we wspomnianym wcześniej przykładzie grafiki komputerowej, w aplikacjach CAD zmieniające się dane wejściowe są często przechowywane w dynamicznych strukturach danych, co można wykorzystać do przyspieszenia zapytań typu punkt w wielokącie.

W niektórych kontekstach problemów związanych z zapytaniami istnieją uzasadnione oczekiwania co do sekwencji zapytań, które mogą być wykorzystywane albo do wydajnych struktur danych, albo do ciaśniejszych oszacowań złożoności obliczeniowej. Na przykład w niektórych przypadkach ważne jest, aby znać najgorszy przypadek dla łącznego czasu dla całej sekwencji N zapytań, a nie dla pojedynczego zapytania. Zobacz także „ analiza zamortyzowana ”.

Numeryczna geometria obliczeniowa

Główny artykuł: komputerowe wspomaganie projektowania geometrycznego

Ta gałąź jest również znana jako modelowanie geometryczne i projektowanie geometryczne wspomagane komputerowo (CAGD).

Podstawowe problemy to modelowanie i reprezentacja krzywych i powierzchni.

Najważniejszymi instrumentami są tu parametryczne krzywe i parametryczne powierzchnie , takie jak krzywe Béziera , spline krzywych i powierzchni. Ważnym podejściem nieparametrycznym jest metoda poziomowania .

Obszary zastosowań geometrii obliczeniowej obejmują przemysł stoczniowy, lotniczy i motoryzacyjny.

Zobacz też

Bibliografia

  1. ^ Franco P. Preparata i Michael Ian Shamos (1985). Geometria obliczeniowa - wprowadzenie . Springer-Verlag . Numer ISBN 0-387-96131-3. Wydanie I; II druk, poprawione i rozszerzone, 1988.
  2. ^ AR Forrest, „Geometria obliczeniowa”, Proc. Royal Society London , 321, seria 4, 187-195 (1971)
  3. ^ Jewgienij B. Karasik (2019). Optyczna geometria obliczeniowa . Numer ISBN 979-8511243344.
  4. ^ S. Khuller i Y. Matias. Prosty algorytm losowego sita dla problemu najbliższej pary . Inf. Komputer, 118(1):34—37,1995 ( PDF )
  5. ^ S. Fortune i JE Hopcroft. — Notatka o algorytmie najbliższego sąsiada Rabina. Listy do przetwarzania informacji, 8(1), s. 20—23, 1979

Dalsza lektura

Czasopisma

Kombinatoryczna/algorytmiczna geometria obliczeniowa

Poniżej znajduje się lista najważniejszych czasopism, które publikują badania dotyczące algorytmów geometrycznych. Proszę zauważyć, że wraz z pojawieniem się czasopism poświęconych specjalnie geometrii obliczeniowej zmniejszył się udział publikacji geometrycznych w czasopismach ogólnego przeznaczenia z zakresu informatyki i grafiki komputerowej.

Zewnętrzne linki

Posłuchaj tego artykułu ( 9 minut )
Mówiona ikona Wikipedii
Ten plik audio został utworzony na podstawie rewizji tego artykułu z dnia 17 września 2013 r. i nie odzwierciedla kolejnych edycji. ( 17.09.2013 )
( Pomoc audio  · Więcej artykułów mówionych )