Online Courses 
Coursera
Moocable is learner-supported. When you buy through links on our site, we may earn an affiliate commission.
Description
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. 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.
Tags
Syllabus
- 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.
-
TypeOnline Courses
-
ProviderCoursera
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. 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.
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.
- 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.
Tags
Related Courses
Quot erat demonstrandum. Curso cero de Matemáticas
Statistical Learning with R
STAT 507: Epidemiological Research Methods
Computational Probability and Inference
Precalculus: Relations and Functions
Summary Statistics in Public Health
C# and Shader Tutorials for the Unity Engine
Random Variables & Distributions
Logic II
Alberta Education Diploma - Mathematics 30-1: Exam Prep & Study Guide
FTCE General Knowledge Test (GK) (082) Prep
Loading...
Saving...
Loading...