Courses

Course

Computer - Computational Geometry

Indian Institute of Technology Delhi

This course on Computational Geometry provides an in-depth understanding of the essential algorithms and techniques used to solve geometric problems that arise in various fields such as computer graphics, computer-aided design, and geographic information systems.

The curriculum is divided into several modules, each focusing on specific concepts, including:

  • Visibility Problems: Learn how to determine what is visible from a particular point in a geometric space.
  • Line Sweep Method: Understand the powerful technique for solving intersection problems through sweeping a line across the plane.
  • Convex Hull Algorithms: Gain insights into different methods for computing the convex hull of a set of points.
  • Voronoi Diagrams and Delaunay Triangulation: Discover the properties and applications of Voronoi diagrams and their relationship with triangulation.
  • Range Searching: Explore various techniques for efficiently querying points in geometric spaces.
  • Epsilon-Nets and VC Dimension: Understand advanced topics in computational geometry related to approximation and set covers.

Throughout the course, students will engage with theoretical concepts and practical applications, solidifying their understanding through real-world examples. By the end of the course, participants will be equipped with the tools necessary to address complex geometric problems effectively.

Course Lectures
  • Mod-01 Lec-01 Introduction
    Mod-01 Lec-01 Introduction
    Prof. Sandeep Sen
    Play

    This module introduces the fundamental concepts of Computational Geometry. Students will explore the role of geometry in computer science, including its applications in graphics, robotics, and geographic information systems.

    Key topics include:

    • Definition of Computational Geometry
    • Historical background
    • Importance in various fields
  • Mod-01 Lec-02 Visibility Problems
    Mod-01 Lec-02 Visibility Problems
    Prof. Sandeep Sen
    Play

    This module focuses on visibility problems within computational geometry. Students will learn how to determine which objects are visible from a given viewpoint and the implications of visibility in various applications.

    Topics covered include:

    • Definition of visibility problems
    • Algorithms for visibility determination
    • Applications in robotics and computer graphics
  • Mod-02 Lec-03 2D Maxima
    Mod-02 Lec-03 2D Maxima
    Prof. Sandeep Sen
    Play

    This module delves into the concept of 2D Maxima, which involves finding the maximum points in a two-dimensional space based on specific criteria. Students will learn various algorithms used to solve this problem efficiently.

    Key areas explored include:

    • Definition of 2D Maxima
    • Algorithmic approaches
    • Real-world applications
  • Mod-03 Lec-04 Line Sweep Method
    Mod-03 Lec-04 Line Sweep Method
    Prof. Sandeep Sen
    Play

    The Line Sweep Method is a powerful algorithmic technique used to solve various geometric problems. In this module, students will learn how to implement this method effectively to handle problems such as intersection detection and area calculations.

    Topics will include:

    • Concept of line sweeping
    • Implementation details
    • Common applications in geometry
  • Mod-03 Lec-05 Segment Intersection Problem
    Mod-03 Lec-05 Segment Intersection Problem
    Prof. Sandeep Sen
    Play

    This module covers the Segment Intersection Problem, wherein students will learn how to efficiently determine the intersection points of line segments. The importance of this problem in computer graphics and geographic information systems is emphasized.

    Key learning points include:

    • Definition of the Segment Intersection Problem
    • Algorithms for solving this problem
    • Applications in real-world scenarios
  • Mod-03 Lec-06 Line Sweep: Rectangle Union
    Mod-03 Lec-06 Line Sweep: Rectangle Union
    Prof. Sandeep Sen
    Play

    In this module, the concept of Rectangle Union using the Line Sweep method is introduced. Students will understand how to compute the union of multiple rectangles and the algorithmic considerations involved.

    Topics include:

    • Understanding Rectangle Union
    • Line Sweep application for rectangles
    • Complexity analysis and optimization
  • Mod-04 Lec-07 Convex Hull
    Mod-04 Lec-07 Convex Hull
    Prof. Sandeep Sen
    Play

    This module introduces the Convex Hull concept, a fundamental problem in computational geometry. Students will learn methods to compute the convex hull of a set of points and understand its importance in various applications.

    Key topics include:

    • Definition and significance of Convex Hull
    • Algorithms for computing Convex Hull
    • Applications in computer graphics and data analysis
  • Mod-04 Lec-08 Convex Hull Contd
    Mod-04 Lec-08 Convex Hull Contd
    Prof. Sandeep Sen
    Play

    This module continues the exploration of the Convex Hull concept, focusing on advanced algorithms and techniques for efficient computation. Students will enhance their understanding of different approaches to finding convex hulls.

    Topics covered include:

    • Advanced algorithms for Convex Hull
    • Comparative studies of techniques
    • Real-world applications
  • Mod-04 Lec-09 Quick Hull
    Mod-04 Lec-09 Quick Hull
    Prof. Sandeep Sen
    Play

    This module introduces the Quick Hull algorithm, an efficient method for computing the convex hull of a set of points. Students will learn how this algorithm operates and its advantages over other methods.

    Key areas of focus include:

    • Understanding the Quick Hull algorithm
    • Implementation details
    • Advantages and applications
  • Mod-04 Lec-10 More Convex Hull Algorithms
    Mod-04 Lec-10 More Convex Hull Algorithms
    Prof. Sandeep Sen
    Play

    This module explores various algorithms for computing the Convex Hull, highlighting multiple approaches and their respective complexities. Students will engage in comparative analysis to determine the best method for different scenarios.

    Topics include:

    • Overview of Convex Hull algorithms
    • Complexity analysis of each method
    • Real-world applications and implications
  • Mod-05 Lec-11 Intersection of Half Planes and Duality
    Mod-05 Lec-11 Intersection of Half Planes and Duality
    Prof. Sandeep Sen
    Play

    This module discusses the intersection of half-planes and the concept of duality in computational geometry. Students will learn about the significance of these concepts in solving geometric problems efficiently.

    Key topics include:

    • Definition of half-planes and intersection
    • Understanding duality
    • Applications in geometric algorithms
  • Mod-05 Lec-12 Intersection of Half Planes and Duality Contd
    Mod-05 Lec-12 Intersection of Half Planes and Duality Contd
    Prof. Sandeep Sen
    Play

    This module continues the exploration of half-plane intersection and duality, focusing on advanced techniques and strategies for efficient computation. Students will engage with complex problems and their solutions.

    Topics will include:

    • Advanced methods for half-plane intersection
    • Duplex algorithms
    • Real-world applications and case studies
  • Mod-06 Lec-13 Lower Bounds
    Mod-06 Lec-13 Lower Bounds
    Prof. Sandeep Sen
    Play

    This module addresses the concept of lower bounds in computational geometry, exploring fundamental principles that dictate the efficiency of geometric algorithms. Students will learn how to establish lower bounds for various geometric problems.

    Topics of focus include:

    • Definition of lower bounds
    • Techniques for establishing bounds
    • Implications for algorithm design
  • Mod-07 Lec-14 Planar Point Location
    Mod-07 Lec-14 Planar Point Location
    Prof. Sandeep Sen
    Play

    This module covers Planar Point Location, a crucial problem in computational geometry. Students will learn algorithms and data structures that help determine the location of points in a planar subdivision.

    Key learning objectives include:

    • Understanding planar subdivisions
    • Algorithms for point location
    • Applications in geographic information systems
  • Mod-07 Lec-15 Point Location and Triangulation Contd...
    Mod-07 Lec-15 Point Location and Triangulation Contd...
    Prof. Sandeep Sen
    Play

    This module continues the study of Point Location and Triangulation, focusing on advanced methods and strategies for efficient point location within triangulated planar subdivisions.

    Topics include:

    • Advanced triangulation techniques
    • Point location algorithms
    • Applications in computer graphics and GIS
  • Mod-08 Lec-17 Voronoi Diagram : Properties
    Mod-08 Lec-17 Voronoi Diagram : Properties
    Prof. Sandeep Sen
    Play

    This module covers Voronoi Diagrams, including their properties and significance in computational geometry. Students will learn how to construct Voronoi diagrams and understand their applications in various fields.

    Key topics include:

    • Definition and properties of Voronoi Diagrams
    • Construction methods
    • Applications in fields like geography and robotics
  • Mod-08 Lec-19 Delaunay Triangulation.
    Mod-08 Lec-19 Delaunay Triangulation.
    Prof. Sandeep Sen
    Play

    This module covers Delaunay Triangulation, a specific type of triangulation that has important properties and applications in computational geometry. Students will learn algorithms for constructing Delaunay triangulations and their significance in various fields.

    Key topics include:

    • Definition and properties of Delaunay Triangulation
    • Algorithms for construction
    • Applications in computer graphics and mesh generation
  • Mod-09 Lec-20 Quick sort and Backward Analysis
    Mod-09 Lec-20 Quick sort and Backward Analysis
    Prof. Sandeep Sen
    Play

    This module discusses Quick Sort and Backward Analysis, focusing on their applications in computational geometry. Students will learn how these methods can optimize geometric algorithms and enhance computational efficiency.

    Key areas covered include:

    • Overview of Quick Sort
    • Backward Analysis techniques
    • Applications in geometric problem-solving
  • Mod-09 Lec-21 Generalized RIC
    Mod-09 Lec-21 Generalized RIC
    Prof. Sandeep Sen
    Play

    This module covers the Generalized RIC, a fundamental concept in computational geometry. Students will explore:

    • The theoretical underpinnings of RIC.
    • Applications in geometric algorithms.
    • Case studies illustrating its usage in various computational contexts.

    Through a mix of lectures and practical examples, learners will gain a deep understanding of generalized RIC and its implications in modern computational tasks.

  • Mod-09 Lec-22 RIC Continued
    Mod-09 Lec-22 RIC Continued
    Prof. Sandeep Sen
    Play

    This module continues the discussion on RIC, delving deeper into its applications and nuances. Key areas of focus include:

    1. Further exploration of RIC techniques.
    2. Advanced applications in problem-solving.
    3. Practical exercises to reinforce learning.

    By the end of this module, students will be well-equipped to utilize RIC in complex computational scenarios.

  • Mod-10 Lec-23 Arrangements
    Mod-10 Lec-23 Arrangements
    Prof. Sandeep Sen
    Play

    The Arrangements module introduces the concept of planar arrangements, exploring their significance in computational geometry.

    Topics include:

    • Theory of arrangements and their properties.
    • Applications in data structures and algorithms.
    • Hands-on examples to illustrate the concepts.

    This module aims to provide a solid foundation in arrangements and their usage in solving geometric problems.

  • Mod-10 Lec-24 Zone Theorem and Application
    Mod-10 Lec-24 Zone Theorem and Application
    Prof. Sandeep Sen
    Play

    This module focuses on the Zone Theorem and its applications in computational geometry. Students will explore:

    • The principles behind the Zone Theorem.
    • Applications in various geometric problems.
    • Case studies that showcase the theorem's utility.

    By the end of this module, students should be able to apply the Zone Theorem to solve real-world computational geometry issues.

  • Mod-10 Lec-25 Levels
    Mod-10 Lec-25 Levels
    Prof. Sandeep Sen
    Play

    This module introduces Levels, a fundamental concept in computational geometry, particularly in the context of arrangements. Key topics include:

    1. Definition and significance of levels in geometric arrangements.
    2. Applications in data structures for efficient searching.
    3. Hands-on examples demonstrating practical applications.

    The aim is to provide students with a solid grounding in the theory and applications of levels in computational geometry.

  • Mod-11 Lec-26 Range Searching : Introduction
    Mod-11 Lec-26 Range Searching : Introduction
    Prof. Sandeep Sen
    Play

    This module serves as an introduction to Range Searching. Students will learn the fundamental concepts and techniques used in this field, which includes:

    • Basic definitions and examples of range searching.
    • Importance of range searching in computational tasks.
    • Overview of algorithms used for efficient range searching.

    The module will equip students with foundational knowledge necessary for further exploration in this area of computational geometry.

  • Mod-11 Lec-27 Orthogonal Range searching
    Mod-11 Lec-27 Orthogonal Range searching
    Prof. Sandeep Sen
    Play

    In this module, students will learn about Orthogonal Range Searching, focusing on its applications and importance in geometric algorithms. Key topics include:

    1. Theoretical foundations of orthogonal range searching.
    2. Practical applications and algorithms.
    3. Hands-on exercises to reinforce learning.

    The objective is to provide students with a thorough understanding of orthogonal range searching and its relevance in computational geometry.

  • Mod-11 Lec-28 Priority Search Trees
    Mod-11 Lec-28 Priority Search Trees
    Prof. Sandeep Sen
    Play

    This module covers Priority Search Trees, a pivotal data structure in computational geometry. Students will examine:

    • The theory behind priority search trees.
    • Applications in range searching and geometric problems.
    • Implementation techniques and challenges.

    By the end of this module, students will have the skills to implement and utilize priority search trees in various computational scenarios.

  • Mod-11 Lec-29 Non - Orthogonal Range Searching
    Mod-11 Lec-29 Non - Orthogonal Range Searching
    Prof. Sandeep Sen
    Play

    This module introduces Non-Orthogonal Range Searching, expanding on traditional range searching methods. Key topics include:

    1. Differences between orthogonal and non-orthogonal techniques.
    2. Applications in various domains of computational geometry.
    3. Practical examples and case studies.

    The goal is to equip students with a broader perspective on range searching techniques and their applications in real-world scenarios.

  • Mod-11 Lec-30 Half - Plane Range Query
    Mod-11 Lec-30 Half - Plane Range Query
    Prof. Sandeep Sen
    Play

    This module focuses on Half-Plane Range Queries, a specialized area in computational geometry. Students will explore:

    • Theoretical concepts behind half-plane queries.
    • Applications in geometric problems and algorithms.
    • Practical exercises to reinforce understanding.

    By completing this module, students will gain the skills necessary to apply half-plane range queries in various computational tasks.

  • Mod-12 Lec-31 Well Separated Partitioning
    Mod-12 Lec-31 Well Separated Partitioning
    Prof. Sandeep Sen
    Play

    This module deals with Well-Separated Partitioning, an important concept in computational geometry. Key areas of focus include:

    1. Definition and significance of well-separated partitions.
    2. Applications in clustering and geometric algorithms.
    3. Case studies highlighting practical uses.

    The objective is to provide students with a comprehensive understanding of partitioning techniques and their applications in real-world scenarios.

  • Mod-12 Lec-32 Quadtrees Epsilon -WSPD
    Mod-12 Lec-32 Quadtrees Epsilon -WSPD
    Prof. Sandeep Sen
    Play

    This module introduces Quadtrees and Epsilon-WSPD, focusing on their significance in spatial data structures. Key topics include:

    • Understanding the structure and function of Quadtrees.
    • Applications of Epsilon-WSPD in computational geometry.
    • Comparative analysis of Quadtrees and other data structures.

    By the end of this module, students will have a solid grasp of Quadtrees and their applications in spatial data management.

  • Mod-12 Lec-33 Construction of Epsilon - WSPD
    Mod-12 Lec-33 Construction of Epsilon - WSPD
    Prof. Sandeep Sen
    Play

    This module focuses on the Construction of Epsilon-WSPD, providing students with the tools and techniques needed for implementation. Key areas include:

    1. Step-by-step guidance on constructing Epsilon-WSPD.
    2. Applications and implications in computational geometry.
    3. Hands-on practical exercises to enhance understanding.

    Students will leave this module with the skills to construct and apply Epsilon-WSPD in various scenarios.

  • Mod-12 Lec-34 Epsilon - WSPD to Geometric Spanner
    Mod-12 Lec-34 Epsilon - WSPD to Geometric Spanner
    Prof. Sandeep Sen
    Play

    This module discusses the conversion of Epsilon-WSPD to Geometric Spanners, focusing on their relevance in computational geometry. Topics include:

    • Theoretical underpinnings of geometric spanners.
    • Applications of Epsilon-WSPD in creating spanners.
    • Case studies demonstrating practical implementations.

    By the end of this module, students will understand how to convert Epsilon-WSPD into useful geometric structures.

  • Mod-13 Lec-35 Epsilon-Nets & VC Dimension
    Mod-13 Lec-35 Epsilon-Nets & VC Dimension
    Prof. Sandeep Sen
    Play

    This module covers Epsilon-Nets and VC Dimension, essential concepts in computational geometry. Students will delve into:

    1. Definitions and theoretical foundations of Epsilon-Nets.
    2. The relationship between Epsilon-Nets and VC Dimension.
    3. Applications in machine learning and geometric problems.

    By completing this module, students will have a solid understanding of these concepts and their significance in computational tasks.

  • Mod-13 Lec-36 Epsilon-Nets & VC Dimension contd
    Mod-13 Lec-36 Epsilon-Nets & VC Dimension contd
    Prof. Sandeep Sen
    Play

    This module continues the discussion on Epsilon-Nets and VC Dimension, providing deeper insights and applications. Key topics include:

    • Advanced concepts in Epsilon-Nets and their properties.
    • Real-world applications in various fields.
    • Practical exercises to consolidate understanding.

    Students will leave this module with a comprehensive understanding of advanced Epsilon-Nets and their implications.

  • Mod-13 Lec-37 Geometric Set Cover
    Mod-13 Lec-37 Geometric Set Cover
    Prof. Sandeep Sen
    Play

    This module discusses Geometric Set Cover, a critical topic in computational geometry. Students will learn about:

    1. Definition and significance of Geometric Set Cover.
    2. Algorithms used for solving set cover problems.
    3. Case studies demonstrating applications in various fields.

    By the end of this module, students will understand how to apply set cover algorithms in practical situations.

  • Mod-13 Lec-38 Geometric Set Cover (with Bounded VC Dimension)
    Mod-13 Lec-38 Geometric Set Cover (with Bounded VC Dimension)
    Prof. Sandeep Sen
    Play

    This module covers Geometric Set Cover with Bounded VC Dimension, exploring its unique features and applications. Key topics include:

    • Understanding the concept of bounded VC dimension.
    • Applications in machine learning and data analysis.
    • Techniques for solving bounded set cover problems.

    Students will gain valuable insights into the relationship between geometric set cover and VC dimension, enhancing their problem-solving skills.

  • Mod-14 Lec-39 Shape Representation
    Mod-14 Lec-39 Shape Representation
    Prof. Sandeep Sen
    Play

    This module introduces Shape Representation, focusing on methods for representing geometric shapes computationally. Key areas include:

    • Various techniques for shape representation.
    • Applications in computer graphics and animation.
    • Case studies illustrating practical implementations.

    By the end of this module, students will understand different methods for representing shapes and their relevance to computational geometry.

  • Mod-14 Lec-40 Shape Comparison
    Mod-14 Lec-40 Shape Comparison
    Prof. Sandeep Sen
    Play

    This module discusses Shape Comparison, an essential area in computational geometry. Students will explore:

    1. Methods for comparing geometric shapes.
    2. Applications in pattern recognition and computer vision.
    3. Case studies that highlight practical applications.

    By completing this module, students will acquire the necessary skills to effectively compare shapes in various computational contexts.

About | Terms | Privacy | Contact Us | Schools
© 2009-2025 Courses.com. All rights reserved.