Share Description
This course presents an introduction to computational geometry, a branch of algorithm theory concerned with the solution of problems involving geometric objects. Its applications include computer graphics, computer-aided design, geographic information systems, robotics, and a variety of others. You will learn to apply various algorithmic approaches to this end, as well as assess their strengths and weaknesses in a specific context, gaining the ability to select the most appropriate method for a specific problem.
Syllabus :
1. Point inclusion in a polygon
- Problem statement
- Testing point inclusion in a polygon
- Algorithmic details
- Degenerate cases
- Putting everything together
- Convex polygons
- Testing point inclusion in a convex polygon
- Star-shaped polyogns
2. Convex hulls
- Convex hull of a planar point set
- A naïve algorithm
- Modified Graham's algorithm
- Graham's scan
- Jarvis march
- Divide and conquer
- Incremental algorithms
- Quick hull
- Chan's algorithm
3. Intersections
- Line segment intersections
- Plane sweep
- Data structures
- An algorithm for intersecting line segments
- The algorithm complexity
- Polygon intersection
4. Polygon triangulation
- A diagonal
- Traingulation: definition and properties
- A naïve algorithm
- Graph dual to a triangulation
- An ear-cutting algorithm
- Monotone polygons
- Triangulating a monotone polygon
5. Orthogonal range search
- Motivation and problem statement
- 1-dimensional range search
- Querying a 1-dimensional range tree
- Range trees
- Constructing and querying range trees
- Fractional cascading
- Layered range trees
- Priority search trees
- Querying a priority search tree
