Logo_iSurf_org

Subscribe
to eAlerts

for Geom Site
Updates

CLICK HERE

 

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

 

Combinatorics

- 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)
 

Visibility

- 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
 

Reconstruction

- 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