Алгоритми у геометрији

Студије
Докторске академске студије (1. семестар)
Предавања
Милица Стојановић, Милица Вучковић
Вежбе
Небојша Николић, Марија Боричић, Нада Младеновић, Душан Џамић

Циљ предмета је упознавања и решавање геометријских проблема помоћу рачунара.

Теоријска настава

  1. Аранжмани хиперравни. Бројање пљосни и инциденција. Бројање тачака.
  2. Зоне у аранжманима. Конструкција аранжмана.
  3. Графови. Проблем визуелизације у графу (проблем налажења најкраћег пута).
  4. Налажење највећег конвексног подскупа у равни, простору, n-дим. простору.
  5. Конструкција конвексног затворења у равни, простору, n-дим. простору.
  6. Налажење најближих суседа у равни, простору, n-дим. простору.
  7. Воронојев дијаграм у равни, простору, n-дим. простору.
  8. Примена Воронојевог дијаграма у равни: „Post Office” проблем.
  9. Примена Воронојевог дијаграма у простору.
  10. Полигон: алгоритми за триангулацију; триангулација помоћу Воронојевог дијаграма.
  11. Полиедар: Када је триангулација могућа?
  12. Минимална и максимална триангулација. Триангулација скупа тачака у простору.
  13. n-димензиона триангулација. Хиперкоцка.
  14. Проблеми у вишедимензионим просторима. Примена Воронојевих дијаграма.

Студијски истраживачки рад

  1. Креирање нових програма за познате геометријске проблеме и упоређивање са постојећим програмима. 
  2. Испитивање нових геометријских проблема помоћу рачунара. 
  3. Израда семинарског рада.


Литература

  • Edelsbrunner, H. Algorithms in Combinatorial Geometry, Springer – Verlag, Heidelberg, 1987
  • Драган Ацкета, Снежана Матић – Кекић, Геометрија за информатичаре, Универзитет у Новом Саду, Природно - математички факултет, Нови Сад, 2000.
  • Trott, Michael, The Mathematica guide book for graphics, Springer, 2004.
  • Foley, James, Computer Graphics, Addison-Wesley, 1996.

© 2017 Катедра за математику| Факултет организационих наука | Универзитет у Београду