Geometric Algorithms
Geometric algorithms are a category of computational methods used to solve problems related to geometric shapes and their properties. These algorithms deal with objects like points, lines, polygons, and other geometric figures. 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.
Monthly Subscription Starting at AED 99 + VAT
- Level Professional
- Duration 18 hours
- Course by EIT Digital
-
Offered by
About
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. Goals: At the end of this course participants should be able - to decide which algorithm or data structure to use in order to solve a given basic geometric problem, - to analyze new problems and come up with their own efficient solutions using concepts and techniques from the course. Prerequisites: In order to successfully take this course, you should already have a basic knowledge of algorithms and mathematics. Here's a short list of what you are supposed to know: - O-notation, Ω-notation, Θ-notation; how to analyze algorithms - Basic calculus: manipulating summations, solving recurrences, working with logarithms, etc. - Basic probability theory: events, probability distributions, random variables, expected values etc. - Basic data structures: linked lists, binary search trees, etc. - Graph terminology - Programming skills for practical assignments Most of the material in this course is based on the following book: M. de Berg, O. Cheong, M. van Kreveld, and M. Overmars. Computational Geometry: Algorithms and Applications (3rd edition). Springer-Verlag, 2008. It is not mandatory to buy this book. However if participants want to know more than is offered in this course or want to have another look at the material discussed in the lectures, we recommend buying this book. The video lectures contain a few very minor mistakes. A list of these mistakes can be found under resources. If you think you found an error, report a problem by clicking the square flag at the bottom of the lecture or quiz where you found the error.Modules
Introduction
-
1
Videos
1
Videos
- Introduction
Plane Sweep: Concept
-
1
Videos
-
1
Assignment
1
Assignment
- Plane Sweep: Concept
1
Videos
- Plane Sweep: Concept
Data Structures for Plane Sweep Algorithms
-
1
Videos
-
1
Assignment
1
Assignment
- Data Structures for Plane Sweep Algorithms
1
Videos
- Data Structures for Plane Sweep Algorithms
Line Sweep: Missing Parts
-
1
Videos
-
1
Assignment
1
Assignment
- Line Sweep: missing parts
1
Videos
- Line Sweep: Missing Parts
Programming: Plane Sweep Algorithms
-
1
Discussion
-
2
Programming
- Plane sweep algorithm for line segment intersection
- Plane sweep algorithm for line segment intersection: Additional Input
1
Discussions
- Experimental evaluation of algorithm
Wrap-Up Quiz
-
1
Assignment
1
Assignment
- Line Sweep Algorithms
Voronoi Diagrams
-
1
Videos
1
Videos
- Voronoi Diagrams
Voronoi Diagrams: Structure
-
1
Videos
1
Videos
- Voronoi Diagrams: Structure
Complexity of Voronoi Diagrams
-
1
Videos
-
1
Assignment
1
Assignment
- Voronoi
1
Videos
- Complexity of Voronoi Diagrams
Delaunay Triangulations
-
1
Videos
1
Videos
- Delaunay Triangulations
Angle-Optimal Triangulations
-
1
Videos
1
Videos
- Angle-Optimal Triangulations
Legal Triangulations
-
1
Videos
-
1
Assignment
1
Assignment
- Triangulations
1
Videos
- Legal Triangulations
Randomized Incremental Construction
-
1
Videos
1
Videos
- Randomized Incremental Construction
Randomized Incremental Construction: Analysis
-
1
Videos
-
1
Assignment
1
Assignment
- Randomized incremental construction
1
Videos
- Randomized Incremental Construction: Analysis
Programming: Voronoi Diagrams and Delaunay Triangulations
-
1
Discussion
-
2
Programming
- Legalizing triangulations
- Legalizing triangulations (Additional Inputs)
1
Discussions
- Optional programming assignment
Wrap-Up Quiz
-
1
Assignment
1
Assignment
- Voronoi Diagrams and Delaunay triangulations
Introduction to Range Searching
-
1
Videos
1
Videos
- Introduction to Range Searching
1D Range Searching
-
1
Videos
1
Videos
- 1D Range Searching
KD Trees
-
1
Videos
1
Videos
- KD Trees
Queries in KD-Trees
-
1
Videos
-
1
Assignment
1
Assignment
- KD-trees
1
Videos
- Queries in KD-Trees
Range Trees
-
1
Videos
1
Videos
- Range Trees
Range Trees: Extensions
-
1
Videos
-
1
Assignment
1
Assignment
- Range Trees
1
Videos
- Range Trees: Extensions
Programming: Orthogonal Range Searching
-
1
Discussion
1
Discussions
- Optional programming assignment
Wrap-Up Quiz
-
1
Assignment
1
Assignment
- KD and range trees
Auto Summary
Geometric Algorithms is a professional-level course focused on computational techniques for solving geometric problems involving shapes like points, lines, and polygons. Taught by experts at Coursera, it covers essential algorithms and data structures used in fields such as robotics, computer graphics, and GIS. Learners will gain the ability to select and analyze suitable algorithms for geometric problems. A background in basic algorithms, calculus, probability, data structures, and programming is required. The course spans approximately 1080 minutes and offers both Starter and Professional subscription options. Ideal for data science and AI enthusiasts looking to deepen their knowledge in geometric computations.
Kevin Buchin