Geometria Obliczeniowa

Opis zajęć

Często gdy pytamy informatyka czym się interesuje odpowiada: "Informatyką i matematyką, ale nie geometrią". Te warsztaty mają na celu udowodnienie, że geometria też może być interesująca - o ile jest to geometria obliczeniowa. Zobaczymy zastosowanie geometrii obliczeniowej w problemach na pozór bardzo nie-geometrycznych. Poznamy interesujące struktury danych, przydatne w rozwiązywaniu problemów z geometrii obliczeniowej.
Gdyby nam się nudziło zobaczymy jak zrobić żeby nie liczyć za dużo - a konkretniej po co nam liczby zespolone, i jak znaleźć styczną do dwóch okręgów w kilku zaledwie liniach kodu. Zobaczymy rozwiązania wielu problemów geometrycznych - każde błyskotliwe, i interesujące w swojej prostocie.

Program

  • Struktury danych użyteczne w rozwiązywaniu problemów geometrycznych (Drzewa, drzewa, drzewa…)
  • Rozwiązania interesujących problemów geometrycznych (m. in. triangulacja wielokąta w czasie $O(n log n)$
  • Triangulacja Delaunay - i zastosowania, zastosowania, zastosowania… (Ale to tylko opcjonalnie).
  • Przestrzeń dualna - mapujemy proste na punkty, punkty na proste - i patrzymy na nasz problem trochę inaczej.
  • Geometryczne rozwiązania pozornie nie-geometrycznych problemów.
  • Rozsądna implementacja geometrii.

Wymagania

Obycie algorytmiczne, podstawy geometrii obliczeniowe - ot chociażby co to jest wypukła otoczka i jak się to je.

Kwalifikacja

Opracuj algorytm który rozwiązuje następujący problem:

Mamy dane lusterka na płaszczyźnie, oraz punkty A i B - każde lusterko jest odcinkiem domkniętym na tej płaszczyźnie. Lusterka są ponumerowane i zadane w ustalonej kolejności. Z punktu A chcemy wystrzelić promień lasera tak, aby poodbijał się od WSZYSTKICH lusterek w tej ustalonej kolejności, i po wszystkich odbiciach doleciał do punktu B. Od każdego lusterka promień lasera musi odbić się dokładnie raz. Wypisz czy jest to możliwe, jeśli tak wypisz w jakim kierunku należy wystrzelić promień z punktu A.

Oczekiwana złożoność: $O(n^2)$ lub lepsza.

Mój adres email: jaro3000 miau gmail.com

O ile nie zaznaczono inaczej, treść tej strony objęta jest licencją Creative Commons Attribution-ShareAlike 3.0 License