Basic Geometric Concepts

points, lines, polygons; subdivisions; arrangements; polytopes; cell complexes.

Geometric Searching

fractional cascading; segment tree; interval tree, range tree; priority search tree.

Point Location

slab method; trapezoid method; chain method; bridged chain method.

Plane-Sweep Algorithms

intersection of segments; intersection of rectangles; trapezoidation.

Convex Hulls

2-dimensional convex hull; dynamic convex hull; 3-dimensional convex hull.


closest pair; furthest pair; Voronoi diagrams; triangulations.

Graph Drawing

planar drawings; straight-line drawings; orthogonal drawings; polyline drawings; upward drawings; hierarchical drawings; visibility representations.

This page was last updated on