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
Related Topics for further study
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
IntermediateCourse 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.
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
Alexander S. Kulikov
3.9 Raiting
Dynamics
- 0.0
-
![]()
![]()
![]()
![]()
![]()
Intro course on the dynamics of mechanical systems: geometry of motion, forces causing motion, and predicting dynamic behavior with computational methods....
Mastering Ansys CFD (Level 1)
- 4.3
-
![]()
![]()
![]()
![]()
![]()
Become pro in computational fluid dynamics (CFD) from A to Z using Fluent, CFX, ICEMCFD and Ansys Workbench Last updated: August 19 2021 (Section No....
Computational Geometry
- 3.9
-
![]()
![]()
![]()
![]()
![]()
This course represents an introduction to computational geometry – a branch of algorithm theory that aims at solving problems about geometric objects....
Geometric Algorithms
- 0.0
-
![]()
![]()
![]()
![]()
![]()
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....
