Computational Geometry

Course Purpose
Learn fundamental algorithms in geometric data processing to know important algorithmic paradigms and design and analysis of algorithms.
Learning Goals
Learn bunary searching, divide and conquers, and how to analyze them.
Topic
Session 1Algorithm for determining line intersection: Algorithm paradigm
Session 2Line intersection enumeration algorithm and data structure
Session 3How to write pseudocode and back-of-the-envelope calculations
Session 4Convex hull and its calculation
Session 5Convex hull fast algorithm
Session 6Use of convex polygons: Farthest point pair calculation and collision detection
Session 7Voronoi diagram and its properties
Session 8Voronoi diagram calculation algorithm
Session 9Use of Voronoi diagram: Nearest neighbor search and object skeleton
Session 10Delaunay triangulation and its properties
Session 11Delaunay graph subgraphs and graph spanner
Session 12Object recognition and reconstruction: CRUST algorithm and alpha outline
Session 13Area exploration and ham sandwich cutting
Session 14Ramsey theory and happy ending theorem
Session 15Incidence of points and lines and number of intersections in graph drawing
＊＊This content is based on April 1, 2024. For the latest syllabus information and details, please check the syllabus information inquiry page provided by the university.＊＊