Zaawansowane algorytmy i struktury danych/Ćwiczenia 11

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Zadanie 1

W inkrementalnym problemie otoczki wypukłej chcemy skonstruować algorytm przechowujący zbiór punktów i pozwalający na wykonywanie dwóch operacji:

  • DODAJ - dodaje punkt do zbioru ,
  • ZAWIERA - sprawdza, czy punkt leży wewnątrz otoczki wypukłej zbioru .

Zaproponuj efektywny algorytm dla tego problemu?

Rozwiązanie

Zadanie 2

Niech będą kolejnymi punktami opisującymi wierzchołki zamkniętego wielokąta . Zaproponuj efektywny algorytm sprawdzania, czy dany punkt leży w jego wnętrzu?

Rozwiązanie

Zadanie 3

Pokaż jak w czasie sprawdzić, czy w zbiorze punktów są trzy punkty współliniowe.

Rozwiązanie

Zadanie 4

Triangulacja zbioru punktów to podział otoczki wypukłej na trójkąty w ten sposób, że punkty są wierzchołkami trójkątów. Zaproponuj algorytm wyznaczania triangulacji zbioru punktów .

Rozwiązanie