Built on
polygon
Articles
GEO
Technique
Vectors and orientation
The sign of the cross product is a left or right turn; almost all of computational geometry stands on it.
O(1) per turn
2 problems
GEO
Algorithm
Convex hull
The smallest convex polygon containing all the points, in O(n log n).
O(n log n)
2 problems
GEO
Algorithm
Delaunay triangulation and Voronoi diagram
Zones of the nearest point and triangles with empty circles: two sides of one structure.
O(n log n) on average
2 problems
Problems
Often together
points 3 geodata 3 classic 3 maps and navigation 2 contests 2 intersections 1 numerical precision 1 games 1 interviews 1 hulls 1 sorting 1 stack 1