BD4002 Computational Geometry Syllabus:
BD4002 Computational Geometry Syllabus – Anna University PG Syllabus Regulation 2021
COURSE OBJECTIVES
To understand geometric problems.
To learn the algorithmic solutions for geometric problems.
To learn the solutions for proximity problems
To map problems in various application domains to a geometric problem.
UNIT I INTRODUCTION
Introduction – Application Domains – Line Segment Intersection – Intersection of Convex Polygons – Polygon Triangulation.
UNIT II GEOMETRIC SEARCHING
Geometric Searching – Range Searching – K- d-Trees – Range trees – Point-Location Problems.
UNIT III CONVEX HULL PROBLEM
Convex hull Problem – Preliminaries – Convex Hull Algorithms in the Plane – Graham‟s scan – Jarvis’s March – Quick Hull – Divide-and-conquer – Dynamic Convex Hull Maintenance – Delaunay Triangulation.
UNIT IV PROXIMITY PROBLEMS
Proximity Problems – Fundamental Algorithms (Closest Pair – All Nearest Neighbours – Euclidean Minimum Spanning Tree – Nearest Neighbour Search) – Lower bounds – Closest Pair Problem : A Divide-and-Conquer Approach.
UNIT V VORONOI DIAGRAM
Voronoi Diagram – Proximity Problems Solved by the Voronoi Diagram – Planar Applications.
TOTAL : 45 PERIODS
COURSE OUTCOMES:
Upon completion of this course, the student should be able to
CO1: Transform problems in different applications to geometric problems
CO2: Use algorithms and techniques to solve search and point location problems
CO3: Understand and solve the complex hull problem
CO4: Solve proximity problems using various techniques
CO5: Use the appropriate and relevant, fundamental and applied computational knowledge, methodologies and modern tools in solving real -world problems.
REFERENCES:
1. Dr. Kalyanrao Takale , Dr. Shrikisan Gaikwad , Dr. Mrs. Nivedita Mahajan , Dr. Amjad Shaikh , Prof. Mrs. Shamal Deshmukh , Prof. S.R. Patil,1st Edition,,”Computational Geometry”,2021.
2. David Mount,CMSC 754: Computational Geometry, 2021.Lecture notes from his Fall 2021 computational geometry course at Maryland.
3. Herbert Edelsbrunner, “Algorithms in Combinatorial Geometry, EATCS Monographs in Computer Science”, Springer Verlag, 2011.
WEB REFRENCES:
1. https://nptel.ac.in/courses/106/102/106102011/
2. https://ocw.mit.edu/courses/mechanical-engineering/2-158j-computational-geometry spring-2003/
ONLINE RESOURCES:
1. https://www.hackerearth.com/practice/notes/computational-geometry-i-1/
2. https://algorithmtutor.com/Computational-Geometry/