Computational Geometry

Geometric predicates are algorithmic foundations

Many geometric algorithms depend on the orientation of three points. In the plane, the sign of (bx-ax)(cy-ay) - (by-ay)(cx-ax) distinguishes a left turn, right turn or collinearity. A tiny numerical error in this sign can corrupt a combinatorial structure even when coordinates look visually close. Separate exact logical predicates from approximate constructions, and explicitly handle degeneracies such as equal points, overlapping segments and several events at one coordinate.

References: 2026–27 graduate calendar alignment with a linked Fall 2009 instructor outline · CGAL: official Computational Geometry Algorithms Library manual

Convex hulls and scan invariants

The convex hull is the smallest convex set containing the input points. A monotone-chain algorithm sorts points lexicographically, builds lower and upper chains and removes the most recent point whenever it violates the required turn direction. Sorting dominates the O(n log n) running time, while each point is pushed and popped only a constant number of times. Decide whether collinear boundary points should all be retained; that choice changes the turn test but not the underlying goal.

References: 2026–27 graduate calendar alignment with a linked Fall 2009 instructor outline · CGAL: official Computational Geometry Algorithms Library manual

Sweep-line algorithms maintain changing order

A sweep-line method processes geometric events in coordinate order while maintaining relevant active objects. For segment intersection, events can include endpoints and discovered crossings. The active order changes at crossings, so event handling and status maintenance must agree. The benefit comes from examining geometrically adjacent candidates rather than every pair. A proof must explain why every true intersection eventually becomes a tested candidate and how simultaneous or degenerate events are treated.

References: 2026–27 graduate calendar alignment with a linked Fall 2009 instructor outline · CGAL: official Computational Geometry Algorithms Library manual

Polygon triangulation and planar structure

A simple polygon with n vertices can be partitioned into n - 2 triangles by adding noncrossing diagonals. This count follows from planar structure and provides a useful output check. Not every apparent diagonal lies inside a concave polygon, so visibility matters. Triangulations support rendering, point location and path planning, but an arbitrary triangulation is not automatically a Delaunay triangulation. State whether the input is a simple polygon, a point set or a domain with holes.

References: 2026–27 graduate calendar alignment with a linked Fall 2009 instructor outline · CGAL: official Computational Geometry Algorithms Library manual

Preprocessing for point-location queries

Point location asks which face of a planar subdivision contains a query point. Preprocessing can trade memory and construction time for fast repeated queries. A hierarchy narrows the search through progressively finer subdivisions, while other methods exploit persistent sweep states. Boundary cases require a convention: a point on an edge may belong to the edge itself rather than either adjacent open face. Report preprocessing, query time and storage separately when comparing structures.

References: 2026–27 graduate calendar alignment with a linked Fall 2009 instructor outline · CGAL: official Computational Geometry Algorithms Library manual

Visibility graphs and obstacle-avoiding paths

For polygonal obstacles and a point robot, shortest paths can be studied using obstacle vertices and unobstructed line-of-sight segments. Include the start and goal along with obstacle vertices in the visibility graph, assign Euclidean edge lengths and run a shortest-path algorithm. A robot with nonzero extent requires a configuration-space treatment rather than pretending it is a point. Likewise, adding turning-radius or dynamic constraints changes the feasible path set; a geometrically shortest polyline may not be physically executable.

References: 2026–27 graduate calendar alignment with a linked Fall 2009 instructor outline · CGAL: official Computational Geometry Algorithms Library manual

Worked orientation and algorithm checks

For a = (0,0), b = (3,0) and c = (1,2), the orientation determinant is 3 × 2 - 0 × 1 = 6, a left turn. Replacing c by (1,-2) gives -6, a right turn. Before scaling a geometric program, test these sign conventions together with collinear and duplicate inputs. Verify structural invariants such as consistent edge adjacency and noncrossing diagonals, because a rendered picture alone can hide topological corruption.

References: 2026–27 graduate calendar alignment with a linked Fall 2009 instructor outline · CGAL: official Computational Geometry Algorithms Library manual

Practice & worked answers

Original exercises for this guide.

Public notes & references

Course sources establish the scope above. Reference materials support the explanations; linked lecture notes and books remain with their authors.

• 2026–27 graduate calendar alignment with a linked Fall 2009 instructor outline ↗Course scope · 2026–27
• CGAL: official Computational Geometry Algorithms Library manual ↗Supplementary primary reference
• Prosenjit Bose: COMP 5008 Fall 2009 outline ↗Historical course scope · Fall 2009