Course Title: Computational Geometry
Full Marks: 45+30
Course No: C.Sc. 562
Pass Marks: 22.5+15
Credit Hours: 3
Nature of the course: Theory +Lab
Course Description:
Computational Geometry is the study of the representation and storage of geometric data and relationships, and the design & implementation and analysis of computational algorithms that operate on geometric data to answer questions of practical interest. In this course fundamental algorithms in computational geometry will be covered. Covered topics include;Elementary geometric objects, line segment intersection, triangulation of polygons, polygon partitioning, convex hull computation in 2D and 3D, proximity problems: Voronoi diagrams , motion path planning, mesh generation, range search
Course Objectives:
Introduce the development of algorithmic tools for solving problems having geometric flavor. Apply such tools for solving problems related to computer graphics, geographic information systems (GIS), robotics, and others‐‐‐in which geometric algorithms play a fundamental role.
Course Content:
Unit1: Arrangements of geometric objects and spatial decomposition
1.1 Representation of points , Lines, Line segments, Ray, Polygon, Visibility inside polygon, Triangulation dual, Mouth and Ear of a polygon, Meisters two ear theorem, Coloring of polygon, Polygon triangulation, Art gallery theorem, Notion of turn tests, Computing area of a polygon, Segment Intersection Computation and detection of segment intersection, Plane‐sweep approach for Segment Intersection (6hrs)
1.2 Diagonal tests, Polygon triangulation: Linear time triangulation, Monotone partitioning, Trapezodalization, Plan‐sweep approach for monotone partitioning, intersection of polygons, Convex Partitioning Problem (CPP), Essential diagonals, Hertel’s Mehlhorns Algorithm for CPP, Optimal convex partitioning (7hrs)
Unit2: Convex Hull Problems
2.1 Convex hull computation in 2D: convex hull of point sets, naïve algorithm, gift‐wrap method, Graham scan algorithm, divide and conquer, quick hull approach, incremental algorithm (8hrs)
2.2 Convex hull computation in 3D: Notion of planar graphs, Doubly Connected Edge List, Eular Theorem, box enclosing problem, gift‐wrap algorithm, divide and conquer approach, incremental algorithm. (4hrs)
Unit3: Proximity Problems and Motion Planning
3.1 Voronoi polygon and Voronoi diagram, Delaunay Triangulation, Relationship between Delaunay triangulation and Voronoi diagrams, Construction of Voronoi diagram, Largest Empty Circle Problem, Nearest Neighbor problem, Computing closest pair of points, using Voronoi diagram to compute closest pairs. (7hrs)
3.2 Range Search, 1D‐Range Searching querying, Kd‐trees, Range Trees, Higher Dimensional Range Trees, (4 hrs)
3.3 Robot Motion Planning, Path planning and motion planning in 2D, visibility graphs, computing shortest paths by using visibility graphs, object growing, Minkwoski Sum, Use of Minkwoski Sum for growing obstacles, Motion planning of point robots, disc robots and polygonal robots. (5hrs)
Unit 4 : Mesh
4.1 Mesh and its types, Algorithms for generation two dimensional mesh, application of Delaunay triangulation and quad‐tree methods for generating meshes, mesh conversion, mesh refinements, (4hrs)
Recommended Books:
- J.O’ Rourke, Computational Geometry in C, Cambridge University Press.
- Mark de Berg, Otfried Cheong, Marc van Kreveld, and Mark Overmars, Computational Geometry: Algorithms and Applications, Springer Berlin Heidelberg
- Handbook of Computational Geometry, JR Sack, J. Urrutia, Elsevier.
