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.
Proximity closest pair; furthest pair; Voronoi
diagrams; triangulations.
Graph Drawing planar drawings; straight-line
drawings; orthogonal drawings; polyline drawings; upward
drawings; hierarchical drawings; visibility representations.
|
