Mathematics / advanced
Computational geometry
Prove geometric algorithms through orientation predicates, combinatorial decompositions, spatial structures, and robustness.
Your route through mathematics
Follow the path or begin with a question. Every lesson is open.
Your place, at your pace. Progress is optional and saved only in this browser when available.
Read / explore / reason
Inside this module
Module 01 advanced
Computational geometry
Prove geometric algorithms through orientation predicates, combinatorial decompositions, spatial structures, and robustness.
- 01
Orientation predicates and exact arithmetic
Make geometric decisions from certified signs, with an explicit input model.
32 min - 02
Convex hulls and output-sensitive bounds
Specify the hull output before comparing sorting, wrapping, and Chan’s algorithm.
32 min - 03
Plane sweep and segment intersections
Maintain a local ordering while defining exactly which intersections are reported.
32 min - 04
Planar subdivisions and point location
Measure the subdivision actually stored and distinguish face queries from boundary queries.
32 min - 05
Voronoi diagrams and nearest neighbors
Build nearest-site regions from distance inequalities and retain the ties.
32 min - 06
Delaunay triangulations and empty circles
Connect exact incircle signs, Voronoi duality, and cocircular refinements.
32 min - 07
Range searching and kd-trees
Separate balanced search depth from the geometry of a multidimensional query.
32 min - 08
Geometric duality and arrangements
Declare the point-line map before translating incidence, order, or complexity.
32 min - 09
Randomized incremental construction
Analyze a fixed input through a random insertion order and a backward certificate.
32 min - 10
Geometric approximation and epsilon-nets
Specify the range family and the guarantee before choosing a small representative set.
35 min