Acquisition of knowledge of geometric algorithms (computational geometry). Upon completion of the
\ncourse, students know how to use basic and more complex geometric data structures and algorithms.
\nThey understand and know how to solve geometric problems related to computational geometry,
\ncomputer graphics, graphical user interface, computer games and similar applications.<\/p>\n
Representation of geometric objects. The problem of determining all intersections of n<\/em> given segments. Implementation of algorithms and data structures covered in lectures. Implementation of a doubly Objectives and outcome Acquisition of knowledge of geometric algorithms (computational geometry). Upon completion of the course, students know how to use basic and more complex geometric data structures and algorithms. They understand and know how … Read more<\/a><\/p>\n Read more<\/a>","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[199],"tags":[],"class_list":["post-13800","post","type-post","status-publish","format-standard","hentry","category-subjects"],"acf":[],"yoast_head":"\n
\nThe problem of determining the closest pair of points among n points. Convex hull in 2D space (Jarvis,
\nGraham’s, divide-and-conquer, quick-hull and randomised algorithm, Kronecker-Seidel’s and Chan’s
\nalgorithm). Planar graphs and doubly connected edge lists (DCEL). Intersections semi-plane and linear
\nprogramming. Dual plane and connection between convex hull and semi-plane cross section. Convex
\nhull in 3D space: (gift-wrapping and incremental algorithm). Polygon triangulation. Voronoi diagrams.
\nDelaunay triangulation. Efficient data structures for range queries. Efficient structures for working with
\nintervals.<\/p>\nPractical classes<\/h5>\n
\nconnected edge list (DCEL) structure used to represent the division of planes into connected
\nsubdomains. Implementation of the algorithm for calculating line arrangement. Implementation of various
\nalgorithms for determining the convex hull, an algorithm for triangulation of a simple polygon, an
\nalgorithm for determining the Voronoi diagram for a given set of points, an algorithm for determining the
\nDelaunay triangulation. Implementation of some data structures: kd-tree, R-tree, interval trees, segment
\ntrees. Design and analysis of algorithms for various problems in the field of geometry using
\ncomputational geometry techniques: sweep line technique, incremental algorithms, dual plane and
\nproblem transformation from problems in the primary plane to problems in the dual plane. Using suitable
\nstructures to solve various computer geometry problems.<\/p>\n","protected":false},"excerpt":{"rendered":"