Chat with us on WhatsAppCall Learnizo

KTU 2024 Scheme · Semester 4 · Program Elective I — Computer Science and Engineering

Computational Geometry (PECST418) Syllabus

Official KTU 2024 Scheme syllabus for Computational Geometry, Semester 4, Program Elective I — Computer Science and Engineering (Computer Science and Engineering).

This page compiles APJ Abdul Kalam Technological University's officially published 2024 Scheme syllabus for Computer Science and Engineering, Semester 4, sourced directly from KTU's official website (ktu.edu.in). Learnizo is an independent online tuition platform and is not affiliated with, endorsed by, or officially connected to APJKTU. The university may revise syllabus content after this page was last updated — always cross-check with the official KTU source for the current, authoritative version.

Course Code

PECST418

Credits

3

Teaching Hours

3:0:0:0 (L:T:P:R)

CIE Marks

40

ESE Marks

60

Exam Duration

2 Hrs. 30 Min.

Prerequisites

GAMAT101, PCCST303

Semester

Semester 4

Course Objective

To develop a solid understanding of the fundamental principles, techniques, and algorithms used in computational geometry, including geometric data structures, convex hulls, Voronoi diagrams, and Delaunay triangulations. To equip students with the skills to apply computational geometry algorithms and techniques to address real-world problems in areas such as computer graphics, robotics, and geographic information systems (GIS).

Module-wise Syllabus

Module 1

9 contact hours

Introduction to Computational Geometry:- Basics of Computational Geometry - Introduction and applications of computational geometry, Geometric objects, and their representations, Basic geometric primitives: points, lines, segments, polygons (Text 1, Chapters 1, 2) Convex Hulls - Definition and properties of convex hulls, Graham's scan algorithm, Jarvis's march (gift wrapping) algorithm, Divide and conquer algorithm for convex hulls (Text 2, Section 33.3) Line Segment Intersection - Problem definition and applications, Plane sweep algorithm, Bentley-Ottmann algorithm (Text 3, Chapter 7)

Module 2

9 contact hours

Polygon Triangulation and Voronoi Diagrams:- Polygon Triangulation - Definition and applications, Triangulation of monotone polygons, Ear clipping method, Chazelle's algorithm (Text 1, Chapter 3) Voronoi Diagrams - Definition and properties, Incremental construction algorithm, Fortune's sweep line algorithm (Text 1, Chapter 7) Delaunay Triangulations - Definition and properties, Relationship with Voronoi diagrams, Bowyer-Watson algorithm, Lawson's flip algorithm (Text 1, Chapter 9)

Module 3

9 contact hours

Range Searching and Point Location:- Range Searching - Problem definition and applications, 1-dimensional range searching, K-dimensional range trees, Fractional cascading (Text 1, Chapter 5) Point Location - Problem definition and applications, Trapezoidal map and randomized incremental algorithm, Kirkpatrick's point location algorithm (Text 1, Chapter 6) Binary Space Partitioning - Definition and applications, BSP trees construction and properties, Use in computer graphics and collision detection (Text 1, Chapter 12)

Module 4

Advanced Topics and Applications:- Arrangements of Lines and Duality - Arrangements of lines and complexity, Zone theorem, Duality transform and its applications (Text 1, Chapter 8) Motion Planning and Geometric Optimization - Problem definition and applications, Visibility graphs and shortest path problems, Art gallery problem, Linear programming in geometry (Text 1, Chapters 10, 11) Computational Geometry in Practice - Computational geometry libraries and software, Applications in robotics, computer graphics, GIS (Text 3, Chapters 9, 10)

Course Outcomes

  • CO1Understand Fundamental Concepts and Applications of Computational Geometry
  • CO2Apply Algorithms for Convex Hulls and Line Segment Intersection Algorithms
  • CO3Perform Polygon Triangulation and Understand Voronoi Diagrams
  • CO4Build Delaunay Triangulations and Range Searching Techniques
  • CO5Apply Advanced Computational Geometry Techniques and Algorithms

Assessment Pattern (CIE: 40 marks, ESE: 60 marks)

Continuous Internal Evaluation (CIE)

Attendance5
Assignment / Microproject15
Internal Examination 1 (Written)10
Internal Examination 2 (Written)10

End Semester Examination (ESE)

Total 60 marks, 2 Hrs. 30 Min.. See the official KTU syllabus document for the exact Part A / Part B question pattern for this course.

Textbooks & Reference Books

Textbooks

  • Computational Geometry: Algorithms and Applications — Mark de Berg, Otfried Cheong, Marc van Kreveld, and Mark Overmars (Springer India, 3/e, 2011)
  • Introduction to Algorithms — Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein (MIT Press, 4/e, 2022)
  • Computational Geometry in C — Joseph O'Rourke (Cambridge University Press, 2/e, 1998)

Reference Books

  • Discrete and Computational Geometry Hardcover — Joseph O'Rourke, Satyan L. Devadoss (Princeton University Press, 1/e,2011)
  • Computational Geometry: An Introduction — Franco P. Preparata, Michael I. Shamos (Springer-Verlag New York Inc, 5/e, 1993)
  • Geometric Algorithms and Combinatorial Optimization — Martin Grötschel, Laszlo Lovasz, Alexander Schrijver (Springer-Verlag Berlin and Heidelberg GmbH & Co. K, 2/e, 1993)

Frequently Asked Questions

How many credits is KTU Computational Geometry (PECST418)?

3 credits, with 3:0:0:0 (L:T:P:R) teaching hours per week, under the KTU 2024 Scheme.

How many modules are in the PECST418 syllabus?

4 modules, 27 total contact hours.

What is the CIE and ESE mark split for this course?

CIE (Continuous Internal Evaluation): 40 marks. ESE (End Semester Examination): 60 marks, 2 Hrs. 30 Min.. Total: 100 marks.

What are the recommended textbooks for PECST418?

Computational Geometry: Algorithms and Applications (Mark de Berg, Otfried Cheong, Marc van Kreveld, and Mark Overmars); Introduction to Algorithms (Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein); Computational Geometry in C (Joseph O'Rourke).

Is this syllabus specific to one branch, or common to others too?

This Semester 4 course is listed under Program Elective I — Computer Science and Engineering at KTU under the 2024 Scheme — check the course header above for which branches it's common to.

Need help with KTU Computational Geometry?

Learnizo offers live, 1-on-1 online tuition for KTU CSE subjects — matched to your exact module and semester.