Název předmětu

• Stránky předmětu: http://service.felk.cvut.cz/courses/X36DPG/
• Přednášející: Vlastimil Havran (web)
• Cvičící: Vlastimil Havran

středa 16:15 - 17:45, 18:00 - 19:30 v KN:E-311

v 10.týdnu, tj.21.4.2010, se píše test (60 min)

možné otázky (sesbíráno z Exfortu, snad si nebudou nárokovat autorská práva :)):

1.) Je dan hyperobdelnik pomoci 2 rohu A[N], B[N] (uhlopricne) a stred hyperkoule S[N]. Spocitej minimalni polomer koule, tak aby obdelnik lezel cely uvnitr.

2.) SAT, vysvetlit, kolik udela testu.

3.) 3 druhy rozdeleni hiearchickejch struktur.

4.) Nejblizsi priblizny soused, co to je, proc funguje.

5.) Algoritmus pro stavbu hiearchicke struktury, jaky se pouzivaj pomocny struktury.

1) Je dan hyperobdelnik pomoci min a max v kazde ose a bod. Napsat algoritmus pro vypocet vzdalenosti bodu od hyperobdelnika.

2) Cenova fuknce pri dotazu do hierarchicke datove struktury.

3) Jake vlastnosti musi mit vzdalenost, co je to metrika a metricky prostor.

4) Napsat vsechny typy objektovych obalek a pozadavky na ne.

5) Jak funguje algoritmus AESA a jakou ma pametovou slozitost. Jaky algoritmus a jak snizuje jeho pametovou slozitost.

1. Výpočet vzdálenosti bodů od AABB v N rozměrech

2. Průsečík přímky a hypersféry v N rozměrech

3. Rozdíl uniformních a neuniformních struktur

4. Je dán hyperobdélník pomocí 2 rohů A[N], B[N] (úhlopříčně) a střed hypersféry S[N]. Spočítej minimální poloměr koule tak, aby obdélník ležel celý uvnitř.

5. SAT, vysvětlit a napsat pseudokód kód, kolik udělá testů pokud se jedná o OBB a kolik pro AABB?

6. 3 druhy rozdělení hierarchických struktur

7. Rozdělení hierarchických struktur, tedy podle uspořádání dat a podle paměti.

8. Nejbližší přibližný soused, co to je a proč to funguje.

9. Algoritmus pro stavbu hierarchické struktury, jaký a k čemu se používají pomocný struktury.

10. Je dán hyperobdélník pomocí min a mex v každé ose a bod. Napsat algoritmus pro výpočet vzdáleností bodu od hyperobdélníka.

11. Cenová funkce při dotazu do hierarchické datové struktury.

12. Jaké vlastnosti musí mít vzdálenost, co je to metrika a metrický prostor.

13. Napsat všechny typy objektových obálek a požadavky na ně.

14. Jak funguje algoritmus AESA a jakou má paměťouvou složitost. Jaký algoritmus a jak snižuje jeho paměťovou složitost.

15. Co je to odhad hustoty pravděpodobnosti (density estimation) a jaký algoritmus se při něm využívá?

pokud by se někomu třeba hodilo.. Geometric DS for CG (.chm, 20MB, @megaupload) - je tam něco málo o octrees, height fields visualization, kd-trees, bvh…