• Overview
• Details
• Exercises

Computational geometry studies algorithms on geometric objects (points, segments, polygons). Core tasks include convex hulls, line sweep for intersections, and range/search structures, with attention to robustness and precision.

• Orientation test (cross product), area, collinearity; handling degeneracies and numeric robustness.
• Convex hull: Graham scan, Andrew’s monotone chain O(n log n); output-sensitive hulls.
• Line segment intersection: sweep line (Bentley–Ottmann), event queue and status structure.
• Closest pair of points: divide-and-conquer O(n log n); plane sweep variant.
• Point-in-polygon and polygon triangulation basics; monotone polygons.
• Range searching: kd-trees, range trees; spatial indexing overview.

1. Implement monotone chain convex hull and test on random points including collinear cases.
2. Implement a sweep-line to report all segment intersections on a small set; verify against brute force.
3. Implement the divide-and-conquer closest pair and compare runtime to O(n^2) baseline.