Presentations

Submitted presentations directory. Names of authors of uploaded presentations are in bold. Do not forget to upload the sources (ppt, tex,…) to brute.
READ THE Presentation hints before!

List of available topics

the specific date may change.

No.	Date	Student	Topic
1.	23. 9.	xxxxxxxx
2.	30. 9.	xxxxxxxx
3.	7.10.		[44] Halfedge data structure in OpenMesh library. Demo of ovelap of planar subdivisions.
3.	7.10.		[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.	14.10.		[9a] Convex Hull of a simple polygon: algorithm of Lee] [PREPARATA 166-171]
4.	14.10.		[9b] Convex Hull of a simple polygon: algorithm of Melkman [PREPARATA 166-171]
5.	21.10.		[8] Beneath-beyond method (horní-dolní) [PREPARATA 131-140].
5.	21.10.		[7] Overmars and van Leeuwen algorithm of dynamic convex hull. [PREPARATA 118-125]. Detailed example.
6.	28.10.		Public holliday
7.	4.11.		[11] Diameter of a point set. [PREPARATA 178-183].
7.	4.11.		[23] (2) Kernel of a Polygon [Lee]
8.	11.11.		[13] Largest empty circle [PREPARATA 248-254]
8.	11.11.		[12] Smallest enclosing circle. [Berg 86-89, Mount20 135-140, PREPARATA 248-254] Impementace
9.	18.11.		[14] k-th order Voronoi diagram. [PREPARATA 242-246].
9.	18.11.		[44] Variants of Voronoi diagram - different metrics, weights and site shapes applets (use appletviewer <url>)
10.	25.11.		[18] D&C Algorithm of Delaunay triangulation: DeWall algorithm. [ Cignoni, Maur '02, 15-17].
10.	25.11.		[43] Quad edge data structure and its usage for storage of DT and VD.[Rourke 147-149,199, Guibas&Stolfi], Overview
11.	2.12.		[25] Algorithm for computation of the perimeter of a union of rectangles. [PREPARATA 340-347]
11.	2.12.		[35] Intersection of convex polygons. [O'Rourke 242-252]
12.	9.12.		[36] Robot motion planning [Berg 283-290]
12.	9.12.		[24] Incremental linear programming [BERG (63-)71-79]
13.	16.12.		[6] Triangular method for planar search (Kirkpatrick's Planar point location) [PREPARATA 57-60, Mount 116-120].
13.	16.12.		[39] Kinetic data structures - introduction - kinetic convex hull Razzazi
14.	6.1.		[37] Partition trees and a simplex method [Berg 335-343]
14.	6.1.		[38] Cutting trees [Berg 346-353]

Literature

[Berg, Mount, O'Rourke, Preparata] viz úvodní stránka

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

[Maur] Maur, P: Delaunay Triangulation in 3D. State of the Art and Concept of Doctoral Thesis, ZCU 2002

Table of Contents

Presentations

List of available topics

Literature