Department of Computer Science & Engineering

University of Ioannina

Computational Geometry

Course Feature
Class Description

Course ID: A4

Unit: DATA SCIENCE AND ENGINEERING – Unit A: Algorithms and Information Technologies

Weekly Hours: 4


ECTS Credits: 7

Course Homepage: 

Description: Line Segment Intersection, the algorithm of Bentley and Ottmann. Convex Hulls in 2 dimensions, the algorithm of Kirkpatrick and Seidel. Convex Hulls in 3 dimensions, randomized incremental construction. Delaunay Triangulation in 2 dimensions, randomized incremental construction, Voronoi diagram. Line arrangements. Duality. Orthogonal Range Searching, kd-trees, range trees. Fractional Cascading. Point Location. Visibility and Guarding. Tetrahedralizations. Interval trees, priority search trees, segment trees. Other topics (e.g., Parametric Search).