{{page>../menu&nofooter&noeditbutton}}

====== Presentations ======
  * [[https://cent.felk.cvut.cz/courses/VGE/presentations/ | Submitted presentations]] directory. Names of authors of uploaded presentations are in bold. <fc #FF0000>Do not forget to upload the sources (ppt, tex,...) to brute.</fc>
  * READ THE [[presentation_hints|Presentation hints]] before!

===== List of available topics =====
/*   * [[https://docs.google.com/spreadsheets/d/1FaFGOcX3q8MyZzQ-ILAtZcaHnmU7Ex-Df-kPcxAmAPI/edit#gid=0 | Thursday (9.15-10.45)]]  */
  * [[https://docs.google.com/spreadsheets/d/1RDvsXKuvYMLmbuFO0z2nfFOv0DWq7b6SYW5gDRjog8E/edit#gid=0 | Thursday (11:00-12:30)]] 
the specific date may change.
/*
<fc #ff0000>Choose a topic and fill your name into this [[https://docs.google.com/spreadsheets/d/1PjS5Tha7LnicwUayXJompZqgYqz_iwo08bV0Su3EHrs/edit?usp=sharing | Google sheet]] </fc>. 
  * If more people want the same topic, try to choose one peacefully
  * Choose topic in week three asap - time is running and you have to have time for prepration

*/

^ No. ^  Date  ^ Student   ^ Topic ^
|   1.| 22. 9. | xxxxxxxx  | | 
|   2.| 29. 9. | xxxxxxxx  | |
|   3.|  6.10. |   | [44] Halfedge data structure in [[https://www.graphics.rwth-aachen.de/software/openmesh/intro/ | OpenMesh]] library. Demo of ovelap of planar subdivisions. | 
| ::: | :::    |   | [1] 2D range tree construction and range tree search [PREPARATA 77-87, Mount (75-)79-81, Berg 99-120]. Focus on a demonstration example or an applet. Do not repeat Lecture 3.|
|   4.| 13.10. | Varga  | [9a] Convex Hull of a simple polygon: algorithm of [[http://cgm.cs.mcgill.ca/%7Eathens/cs601/Lee.html | Lee]]] [PREPARATA 166-171]| 
| ::: | :::    |  Veverková | [9b] Convex Hull of a simple polygon: algorithm of [[http://cgm.cs.mcgill.ca/~athens/cs601/Melkman.html | Melkman]] [PREPARATA 166-171]| 
|   5.| 20.10. | Arameleva | [8] Beneath-beyond method (horní-dolní) [PREPARATA 131-140].| 
| ::: | :::    | Zahradník  | [7] Overmars and van Leeuwen algorithm of dynamic convex hull. [PREPARATA 118-125]. Detailed example.| 
|   6.| 27.10. | Krejčí | [11] Diameter of a point set. [PREPARATA 178-183]. |
| ::: | :::    | Chaloupka | [23] (2) Kernel of a Polygon [{{:courses:cg:presentations:p415-lee.pdf|Lee}}]| 
|   7.|  3.11. | Linder | [13] Largest empty circle [PREPARATA 248-254]  | 
| ::: | :::    | Čuhel | [12] Smallest enclosing circle. [Berg 86-89, Mount20 135-140, PREPARATA 248-254] [[https://colab.research.google.com/drive/17jivLkHEQdTIxVccEe8w5MKfaDC6NK_u?usp=sharing#scrollTo=Jvk9FeNG-F3R |Impementace]]| 
|   8.| 10.11. | Tošner | [14] k-th order Voronoi diagram. [PREPARATA 242-246]. | 
| ::: | :::    | <del>Kraus</del> | <del>[44] Variants of Voronoi diagram - different metrics, weights, and site shapes [[http://www.nirarebakun.com/voro/efpvorocli.html | applets]] (use appletviewer from [[https://www.oracle.com/java/technologies/java-archive-javase10-downloads.html | jdk 10]])</del>| 
|   9.| 17.11. | --- | Public holiday |
|  10.| 24.11. | Cicvárek | [18] D&C Algorithm of Delaunay triangulation: DeWall algorithm. [ {{:courses:cg:dewall.pdf|Cignoni}}, [[courses:cg:links:start#papers_-_local | Maur '02, 15-17]]].  | 
| ::: | :::    | Yongpan Fu | [43] Quad edge data structure and its usage for storage of DT and VD.[Rourke 147-149,199, [[http://www.sccg.sk/~samuelcik/dgs/quad_edge.pdf | Guibas&Stolfi]]], [[http://www.neolithicsphere.com/geodesica/doc/quad_edge_overview.htm | Overview]]|
|  11.|  1.12. | Žižková  | [25] Algorithm for computation of the perimeter of a union of rectangles. [PREPARATA 340-347]| 
| ::: | :::    | Sokovnin | [35] Intersection of convex polygons. [O'Rourke 242-252]| 
|  12.|  8.12. | <del>Kolář</del> |<del>[37] Partition trees and a simplex method [Berg 335-343] </del>|
| ::: | :::    | Velecký  | [36] Robot motion planning [Berg 283-290] | 
|  13.| 15.12. | Hubáček  | [6] Triangular method for planar search (Kirkpatrick's Planar point location) [PREPARATA 57-60, Mount 116-120]. |
| ::: | :::    | Janoušková | [39] Kinetic data structures - introduction - kinetic convex hull {{ :courses:cg:presentations:rs-kchmu-03.pdf |Razzazi}} | 
|  14.| 12.1.  | <del>Kolář</del> | <del>[37] Partition trees and a simplex method [Berg 335-343]</del>| 
| ::: | :::    | Kraus | [44] Variants of Voronoi diagram - different metrics, weights, and site shapes [[http://www.nirarebakun.com/voro/efpvorocli.html | applets]] (use appletviewer from [[https://www.oracle.com/java/technologies/java-archive-javase10-downloads.html | jdk 10]]) | 
/*

|  12.|  8.12. | --- | [36] Robot motion planning [Berg 283-290]| 
| ::: | :::    | --- | [24] Incremental linear programming [BERG (63-)71-79]| 


| ::: | :::    | Kraus | [38] Cutting trees [Berg 346-353]| 
|  14.|  6.1.  | ---       | Předtermín, pokud bude zájem  | 
[21] Overlap of planar subdivisions. [Berg 33-40] 
[16] Algoritmy 3D Delaunayovy triangulace.  [MAUR '02]. 
Task not chosen: 

<del>[3]  BSP trees in 2D and 3D [Mulmuley 372-382, Berg 249-263]</del>

*/


===== Literature =====

[Berg, Mount, O'Rourke, Preparata] viz [[..:start#literature|úvodní stránka]]

[Mulmuley] K. Mulmuley. Computational Geometry: An Introduction Through Randomized Algorithms. Prentice-Hall, New York, 1993

[Maur] Maur, P: {{ :courses:cg:presentations:maur-dt-3d.zip |Delaunay Triangulation in 3D.}} State of the Art and Concept of Doctoral Thesis, ZCU 2002