Computational Geometry

Computational model. Polygon Triangulation (Art Gallery), division into monotonous polygons. Convex hull (CH) in 2 and larger dimensions (gift-wrapping, beneath-beyond), Minkowski sum, implementation issues, degenerate input. Linear programming, Simplex algorithm and reverse search, duality and polarity. Voronoi diagram, reduction to CH, half-edge doubly linked list. Delaunay triangulation, meshing. Segment and line arrangements, zone theorem. Geometric data structure, point location and data mining, orthogonal search, kd- trees, range trees. Curved geometric objects: representation and operations. Geometric software libraries.