ECE539 Computational Geometry

Introduction (Geometric Objects, Intersections, Duality). Polygon Triangulation. Geometric Data Structures (Interval Tree, Priority Tree, Segment Tree, Range Tree, Kd-tree, Quad-Tree). Point Location. Voronoi Diagram. Delauney Triangulation. Binary Space Partitions.

The course introduces to the basic concepts of Computational Geometry. Aims at introducing to the right usage and application of fundamentals data structures and algorithms for solving problems on geometric objects.

Upon successful completion of this course, the student will be able to:

• know the usage of a variety of geometric data structures and algorithms
• compare and understand the characteristics and the performance of geometric data structures and algorithms
• choose the appropriate geometric data structures and sorting algorithms based on criteria related to functionality, time/space complexity and hardware requirements.
• Apply fundamental techniques for designing data structures and algorithms suitable for geometric problems