About this Course

8,090 recent views
Shareable Certificate
Earn a Certificate upon completion
100% online
Start instantly and learn at your own schedule.
Flexible deadlines
Reset deadlines in accordance to your schedule.
Intermediate Level

Basic knowledge of at least one programming language (loops, recursion, input/output). Basic math: proof by induction, proof by contradiction.

Approx. 19 hours to complete
English
Shareable Certificate
Earn a Certificate upon completion
100% online
Start instantly and learn at your own schedule.
Flexible deadlines
Reset deadlines in accordance to your schedule.
Intermediate Level

Basic knowledge of at least one programming language (loops, recursion, input/output). Basic math: proof by induction, proof by contradiction.

Approx. 19 hours to complete
English

Offered by

Placeholder

Saint Petersburg State University

Syllabus - What you will learn from this course

Week
1

Week 1

4 hours to complete

Point inclusion in a polygon

4 hours to complete
9 videos (Total 41 min)
9 videos
1.2 Problem statement4m
1.3 Testing point inclusion in a polygon3m
1.4 Algorithmic details3m
1.5 Degenerate cases2m
1.6 Putting everything together3m
1.7 Convex polygons4m
1.8 Testing point inclusion in a convex polygon6m
1.9 Star-shaped polyogns4m
3 practice exercises
Preliminaries20m
Geometric computing
Polygon hierarchy
Week
2

Week 2

4 hours to complete

Convex hulls

4 hours to complete
9 videos (Total 54 min)
9 videos
2.2 A naïve algorithm5m
2.3 Modified Graham's algorithm10m
2.4 Graham's scan6m
2.5 Jarvis march3m
2.6 Divide and conquer10m
2.7 Incremental algorithms3m
2.8 Quick hull3m
2.9 Chan's algorithm7m
3 practice exercises
Basic observations
Alternative algorithmic approaches
Refinements
Week
3

Week 3

4 hours to complete

Intersections

4 hours to complete
6 videos (Total 52 min)
6 videos
3.2 Plane sweep10m
3.3 Data structures6m
3.4 An algorithm for intersecting line segments11m
3.5 The algorithm complexity9m
3.6 Polygon intersection8m
3 practice exercises
Intersections and plane sweep
Implementation details
Intersecting polygons
Week
4

Week 4

4 hours to complete

Polygon triangulation

4 hours to complete
7 videos (Total 40 min)
7 videos
4.2 Traingulation: definition and properties5m
4.3 A naïve algorithm2m
4.4 Graph dual to a triangulation6m
4.5 An ear-cutting algorithm4m
4.6 Monotone polygons4m
4.7 Triangulating a monotone polygon11m
3 practice exercises
Polygon triangulations: basic properties
Dual graphs
Monotone polygons

Reviews

TOP REVIEWS FROM COMPUTATIONAL GEOMETRY

View all reviews

Frequently Asked Questions

More questions? Visit the Learner Help Center.