# Subject description - A4M39VG

Summary of Study | Summary of Branches | All Subject Groups | All Subjects | List of Roles | Explanatory Notes               Instructions
 A4M39VG Computational Geometry Extent of teaching: 2+2s Guarantors: Roles: PO,V Language ofteaching: CS Teachers: Completion: Z,ZK Responsible Department: 13139 Credits: 6 Semester: Z

Anotation:

The goal of computational geometry is analysis and design of efficient algorithms for determining properties and relations of geometric entities. The lecture focuses on geometric search, point location, convex hull construction for sets of points in d-dimensional space, searching nearest neighbor points, computing intersection of polygonal areas, geometry of parallelograms. New directions in algorithmic design. Computational geometry is applied not only in geometric applications, but also in common database searching problems.

Study targets:

The course is an informal continuation of fundamental data structures and algorithms courses. You will learn geometric algorithms and data structures allowing for effective computations, e.g., localization of area hit by a ray, computation of intersections and triangulation. You will train presentation and professional discussion skills on the seminars. All of it should not be missing in knowledge of educated progressive Master of Science.

Course outlines:

 1 Computational geometry (CG), typical applications, effective algorithm design techniques 2 Geometric searching 3 Geometric searching 2 4 Planar convex hull 5 Convex hull in 3D 6 Voronoi diagram of points 7 Voronoi diagram of line segments. Higher order Voronoi diagrams 8 Triangulations 9 Intersections of line segments and polygons 10 Intersections of polygonal line segments with a rectangular window 11 Arrangements 12 Dual algorithms 13 New directions in algorithmic design 14 Spare lesson

Exercises outline:

 1 Introduction to the form of the seminars, fundamental math. concepts useful in CG.Selection of topics for assignment. 2 Robustness of geometric predicats and constructs. 3 Presentations of the topic assigned, discussion. Evaluation of the presentation materials and evaluation of the speech by classmate students. Ideas for improvements. 4 Presentation of the topic assigned 5 Presentation of the topic assigned 6 Presentation of the topic assigned 7 Presentation of the topic assigned 8 Presentation of the topic assigned 9 Presentation of the topic assigned 10 Presentation of the topic assigned 11 Presentation of the topic assigned 12 Presentation of the topic assigned 13 Assessment 14 Spare

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, 1st ed, 1994 or 2nd ed, 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++.

Webpage:

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

Keywords:

Computational geometry, Discrete geometry, Geometrical algorithms.

Subject is included into these academic programs:

 Program Branch Role Recommended semester MPIB Common courses V – MPOI3 Computer Vision and Image Processing PO 3 MPKME1 Wireless Communication V 3 MPKME5 Systems of Communication V 3 MPKME4 Networks of Electronic Communication V 3 MPKME3 Electronics V 3 MPKME2 Multimedia Technology V 3 MPEEM1 Technological Systems V 3 MPEEM5 Economy and Management of Electrical Engineering V 3 MPEEM4 Economy and Management of Power Engineering V 3 MPEEM3 Electrical Power Engineering V 3 MPEEM2 Electrical Machines, Apparatus and Drives V 3 MPOI4NEW Computer Graphics and Interaction PO 3 MPKYR4 Aerospace Systems V 3 MPKYR1 Robotics V 3 MPKYR3 Systems and Control V 3 MPKYR2 Sensors and Instrumentation V 3

 Page updated 17.6.2019 14:52:47, semester: Z,L/2020-1, L/2018-9, Z,L/2019-20, Send comments about the content to the Administrators of the Academic Programs Proposal and Realization: I. Halaška (K336), J. Novák (K336)