Explore

Computational Geometry

Approx. 19 hours to complete

Save Course

Go to Course

Course Summary

This course covers the fundamental concepts and algorithms of computational geometry, which plays a crucial role in various fields of computer science and engineering.

Key Learning Points

Learn the basics of computational geometry algorithms and concepts
Understand how computational geometry is used in computer science and engineering
Apply computational geometry algorithms to solve real-world problems

Learning Outcomes

Apply computational geometry algorithms to solve real-world problems
Understand the fundamental concepts and algorithms of computational geometry
Learn how computational geometry is used in different fields of computer science and engineering

Prerequisites or good to have knowledge before taking this course

Basic knowledge of mathematics and programming
Familiarity with data structures and algorithms

Course Difficulty Level

Intermediate

Course Format

Online
Self-paced

Similar Courses

Data Structures and Algorithms
Algorithmic Toolbox
Discrete Optimization

Related Education Paths

Related Books

Description

This course represents an introduction to computational geometry – a branch of algorithm theory that aims at solving problems about geometric objects. Its application areas include computer graphics, computer-aided design and geographic information systems, robotics, and many others. You will learn to apply to this end various algorithmic approaches, and asses their strong and weak points in a particular context, thus gaining an ability to choose the most appropriate method for a concrete problem.

We will cover a number of core computational geometry tasks, such as testing point inclusion in a polygon, computing the convex hull of a point set, intersecting line segments, triangulating a polygon, and processing orthogonal range queries. Special attention will be paid to a proper representation of geometric primitives and evaluation of geometric predicates, which are crucial for an efficient implementation of an algorithm. Each module includes a selection of programming tasks that will help you both to strengthen the newly acquired knowledge and improve your competitive coding skills.

Outline

Point inclusion in a polygon
1.1 Introduction
1.2 Problem statement
1.3 Testing point inclusion in a polygon
1.4 Algorithmic details
1.5 Degenerate cases
1.6 Putting everything together
1.7 Convex polygons
1.8 Testing point inclusion in a convex polygon
1.9 Star-shaped polyogns
Preliminaries

Convex hulls
2.1 Convex hull of a planar point set
2.2 A naïve algorithm
2.3 Modified Graham's algorithm
2.4 Graham's scan
2.5 Jarvis march
2.6 Divide and conquer
2.7 Incremental algorithms
2.8 Quick hull
2.9 Chan's algorithm

Intersections
3.1 Line segment intersections
3.2 Plane sweep
3.3 Data structures
3.4 An algorithm for intersecting line segments
3.5 The algorithm complexity
3.6 Polygon intersection

Polygon triangulation
4.1 A diagonal
4.2 Traingulation: definition and properties
4.3 A naïve algorithm
4.4 Graph dual to a triangulation
4.5 An ear-cutting algorithm
4.6 Monotone polygons
4.7 Triangulating a monotone polygon

Orthogonal range search
5.1 Motivation and problem statement
5.2 1-dimensional range search
5.3 Querying a 1-dimensional range tree
5.4 Range trees
5.5 Constructing and querying range trees
5.6 Fractional cascading
5.7 Layered range trees
5.8 Priority search trees
5.9 Querying a priority search tree

Summary of User Reviews

Learn computational geometry with this highly rated course on Coursera. Students have praised the course's thoroughness and practicality.

Key Aspect Users Liked About This Course

The course is highly practical and provides real-world examples and applications for computational geometry.

Pros from User Reviews

Thorough coverage of the subject matter
Engaging and knowledgeable instructors
Real-world applications and examples provided
Great preparation for further study or professional work

Cons from User Reviews

Some users found the course material to be too advanced or difficult to follow
Lack of interaction with instructors or other students
Course structure and pacing could be improved
Limited opportunities for hands-on practice

Recommended for you

计算几何 | Computational Geometry

In this introductory computer science course, explore geometry, develop geometric thinking, and learn geometric algorithms. 体味几何之趣，领悟算法之美 Computational Geometry first appeared on the horizon when M....

Save Course

Convex Optimization

This course concentrates on recognizing and solving convex optimization problems that arise in applications. This course concentrates on recognizing and solving convex optimization problems that arise in applications....

Save Course