Course Information: In many areas of computer science such as robotics, computer graphics, virtual reality, and geographic information systems, it is necessary to store, analyze, and create or manipulate spatial data. This course deals with the algorithmic aspects of these tasks: we study techniques and concepts needed for the design and analysis of geometric algorithms and data structures. Each technique and concept will be illustrated on the basis of a problem arising in one of the application areas mentioned above.

Geometric Algorithms
EIT 数字課程信息
提供方

EIT 数字
EIT Digital is a European education and innovation organisation with a mission to foster digital technology innovation and entrepreneurial talent for economic growth and quality of life. By linking education, research and business, EIT Digital empowers digital top talents for the future.
教學大綱 - 您將從這門課程中學到什麼
Plane Sweep Algorithms
In this module we will discuss an algorithm for line segment intersection that does not only depend on the input size, i.e. the number of line segments, but also on the output size, i.e. the number of intersections. This algorithm uses the Plane Sweep technique, which is applicable to many algorithmic problems in the Euclidean plane.
Voronoi diagrams and Delaunay triangulations
In this module we will introduce the notions of Voronoi diagrams and Delaunay triangulations and its properties. Furthermore we will an algorithm for constructing Delaunay triangulations using the technique of randomized incremental construction. We will see how to analyze these types of algorithms.
Orthogonal range searching
In this module we will introduce the problem of range searching. We will first look at the one dimensional case and later on generalize to higher dimensions. We will see two data structures that allow for range searching, namely KD Trees and Range Trees. We will compare them by looking at construction time, space usage and query time.
常見問題
我什么时候能够访问课程视频和作业?
我购买证书后会得到什么?
Is financial aid available?
完成课程后,我会获得大学学分吗?
還有其他問題嗎?請訪問 學生幫助中心。