Algorithmic Geometry

Block 1

Convex Hull

• What is a convex hull of a set of points?
• How can you naively compute a convex hull?
• What better algorithms are there for computing convex hulls?
• Is it possible to compute a convex hull faster than $O(n\log n)$ or $O(n\log h)$?
• What happens in Graham Scan when the sorting of $P$ is not unique?
• How do the algorithms deal with collinear points?
• What about the robustness of the algorithms? [TODO]

Line Segment Intersections

• How can you naively find all intersections of line segments?
• What technique can you use to compute intersections faster?
• How does the proposed algorithm work?
• What is the running time of the algorithm?
• What edge cases have to be considered?
• Is the algorithm from the lecture always better than the naive one?