Explore

Geometric Algorithms

Approx. 18 hours to complete

Save Course

Go to Course

Course Summary

This course covers the basics of geometric algorithms, including Voronoi diagrams, Delaunay triangulations, and convex hulls. Students will learn how to implement these algorithms in Python and apply them to real-world problems.

Key Learning Points

Gain a deep understanding of geometric algorithms and their applications
Learn how to implement these algorithms in Python
Apply these algorithms to solve real-world problems

Learning Outcomes

Understand the principles and applications of geometric algorithms
Be able to implement geometric algorithms in Python
Apply geometric algorithms to solve real-world problems

Prerequisites or good to have knowledge before taking this course

Basic knowledge of Python programming
Familiarity with basic geometry concepts

Course Difficulty Level

Intermediate

Course Format

Online
Self-paced

Similar Courses

Algorithmic Toolbox
Computational Geometry

Related Education Paths

Notable People in This Field

Jeff Erickson
Boaz Barak

Related Books

Description

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.

Outline

Plane Sweep Algorithms
Introduction
Plane Sweep: Concept
Data Structures for Plane Sweep Algorithms
Line Sweep: Missing Parts
Plane Sweep: Concept
Data Structures for Plane Sweep Algorithms
Line Sweep: missing parts
Line Sweep Algorithms

Voronoi diagrams and Delaunay triangulations
Voronoi Diagrams
Voronoi Diagrams: Structure
Complexity of Voronoi Diagrams
Delaunay Triangulations
Angle-Optimal Triangulations
Legal Triangulations
Randomized Incremental Construction
Randomized Incremental Construction: Analysis
Voronoi
Triangulations
Randomized incremental construction
Voronoi Diagrams and Delaunay triangulations

Orthogonal range searching
Introduction to Range Searching
1D Range Searching
KD Trees
Queries in KD-Trees
Range Trees
Range Trees: Extensions
KD-trees
Range Trees
KD and range trees

Summary of User Reviews

Discover the fascinating world of Geometric Algorithms with Coursera's online course. Students have praised the course for its engaging and informative content, with many noting the practical applications in real-world scenarios. Overall, the course has received high ratings from students.

Key Aspect Users Liked About This Course

The practical applications of the course's content were highly praised by many users.

Pros from User Reviews

Engaging and informative content
Practical applications in real-world scenarios
Well-structured course material
Experienced and knowledgeable instructors
Opportunity to interact with other students in the course

Cons from User Reviews

Some users found the course material to be too advanced
Limited opportunities for one-on-one interaction with instructors
Difficulty in completing assignments within the given time frame
Lack of additional resources for further learning
Occasional technical issues with the online platform

Recommended for you

Computer vision: OpenCV Basics Quick Starter in Python

Start your Deep Learning Computer Vision Endeavor with Strong OpenCV Basics in Python Hi There! Welcome to my new course OpenCV Fundamentals using Python....

Save Course

DIP using MATLAB: Digital Image Processing for Beginners

DIP (Digital Image Processing) using MATLAB course with certification for beginners by Industry experts at TELCOMA g. image enhancement, images segmentation, images registration)....

Save Course

Complete linear algebra: theory and implementation in code

Learn concepts in linear algebra and matrix analysis, and implement them in MATLAB and Python. You need to learn linear algebra!...

Save Course

Remote Sensing Image Acquisition, Analysis and Applications

Welcome to Remote Sensing Image Acquisition, Analysis and Applications, in which we explore the nature of imaging the earth's surface from space or from airborne vehicles....

Save Course