to eAlerts

for Geom Site



What Problems Solved?

by Dan Sunday



What Problems do Geometry Algorithms Solve?

Geometry algorithms solve several classes of problems. First, they provide fundamental methods for representing geometric objects and robustly computing primitive attributes and performing primitive operations on them. Some of the basic methods implemented by this class of algorithms are:

Representation of Geometric Objects

- basic points, lines, segments, and planes
- triangles, tetrahedrons, polygons and polyhedrons
- collections of objects and relations between them
- parametric (especially polynomial) curves and surfaces
- spatial partitions, planar graphs, linked edge lists

Basic Measurements

- distance between any two geometric objects
- area, volume, circumference, surface area, center of mass


Euclidean Constructions

- segmenting (bisection, line division)
- parallels and perpendiculars
- inscribed circles and circumcircles
- tangents (between any two objects)
- regular polytopes

Basic Set Theory

- intersection, union, and differences (of lines, polygons, polyhedrons, etc)
- test for the inclusion of one object (eg: a point) in another (eg: a polyhedron)
- convex hulls (of large point sets)
- tests for simplicity or convexity of polygons and polyhedra



- Euler characteristic, genus, Betti numbers, etc
- arrangments induced by collections of lines or planes

These are foundational algorithms that are used by a second class of higher level algorithms targeted at more specific and complex problems, such as:

Advanced Set Theory

- all intersections of a large set of finite line segments
- constructing binary space partitions (BSPs)
- point location in a spatial partition or arrangement
- range testing (to filter a large set of points)


- internal or external visibility graph of a polygon or polyhedron
- minimal guard positioning (art gallery, security, etc)
- hidden line or surface determination
- ray tracing with intersection and reflection

Partitioning (polygons and polyhedra)

- into convex and monotone pieces
- trapezoidalization and triangulation of polygons
- tetrahedralization of polyhedra

Proximity Determination

- Voronoi regions
- Delaunay triangulation

Path Planning (Robotics)

- collision avoidance among 2D and 3D polytope obstacles
- optimal routes (minimum distance, fastest time, least risk)
- object orientation manipulation (get the piano upstairs)
- linked arm movement : reachability


- of a 3D object from multiple 2D slices or views

Shape Similarity

- measures of similarly & invariants of shape
- template matching & shape comparison

Approximation and Interpolation

- polyline approximation (of other polylines or parametric curves)
- generalization of polyhedral and parametric surfaces
- mesh generation (finite element approximation)
- linear and polynomial interpolation of approximations

Graph Theory

- minimal distance node pairing
- minimum spanning trees
- circuits and cycles (Euler, Hamilton, traveling salesperson)
- optimal drawing of graphs in the plane



© Copyright 2012 Dan Sunday, 2001 softSurfer