Summary of Study | Summary of Branches | All Subject Groups | All Subjects | List of Roles | Explanatory Notes               Instructions

---

XP39VPG	Computational Geometry
Roles:	S	Extent of teaching:	2P+2S
Department:	13139	Language of teaching:
Guarantors:	Felkel P.	Completion:	ZK
Lecturers:	Felkel P.	Credits:	4
Tutors:	Felkel P.	Semester:	Z

Web page:

https://cw.fel.cvut.cz/wiki/courses/cg/start

Anotation:

Principles of computational geometry (CG), data structures and paradigms, methods of geometric search, convex polygons and hulls, applications of convex hull, proximity problems, Voronoi diagrams, triangulation, efficient intersection algorithms, intersection of semispaces and polygonal regions, geometry of rectangles, dual mappings and spaces, convex hull in dual space, algorithms of computer graphics and CG. Students who completed course 36VGE cannot enroll.

Study targets:

Analysis and design of effective algorithms for geometric objects.

Course outlines:

Exercises outline:

Literature:

[1.		Berg, M. de, Cheong, O., Kreveld, M. van, Overmars, M.: Coputational Geometry. Algorithms and Applications, Springer-Verlag, Berlin, 3rd ed., 2008. ISBN: 978-3-540-77973-5
2.		O' Rourke, Joseph: Computational Geometry in C, Cambridge University Press, 1.vydání, 1994 nebo 2.vydání, 2000
3.		Preperata F.P.- M.I.Shamos: Computational Geometry An Introduction. Berlin, Springer-Verlag,1985.

Requirements:

Knowledge of Fundamental sorting and searching algorithms. Linear algebra and fundamentals of computer graphics are advantageous. Programming in C++.

Keywords:

Computational geometry, Discrete geometry.

Subject is included into these academic programs:

Program	Branch	Role	Recommended semester
DOKP	Common courses	S	–
DOKK	Common courses	S	–

---

Page updated 15.1.2025 07:51:13, semester: Z/2025-6, Z,L/2024-5, Send comments about the content to the Administrators of the Academic Programs

Proposal and Realization: I. Halaška (K336), J. Novák (K336)