to eAlerts

for Geom Site



What Applications?

by Dan Sunday



What Applications use Geometry Algorithms ?

There is a good Task Force Report "Application Challenges to Computational Geometry" describing many modern applications of algorithmic geometry. It notes that with the explosion in computer graphics technology, "geometric computing is creeping into virtually every corner of science and engineering". One could add business and finance, education, entertainment to the list. Specific areas that the report considers in detail include:

Computer Graphics and Imaging

uses geometry algorithms to represent, render, and visualize complex real and virtual worlds, such as we often see in recent movies, video games, or training simulators. Basic methods include geometric modeling, clipping, set operations, space partitions, point location, etc. Advanced techniques include visibility determination (hidden surface removal, ray tracing), shadow casting, radiosity, collision detection, and spline and NURBS modeling methods.

Shape Reconstruction

reconstructs computer 3D models of objects from 2D cross-sections or multiple views (such as stereoscopic pairs) of the object. Important specific application areas include medical imaging, microscopy, geology, and remote sensing.

Computer Vision and Recognition

includes model-based (pattern) recognition and the recovery of 3D structure from 2D images (especially using stereoscopic and motion information). This area also includes image segmentation to extract information about objects in a scene.

Geographical Information Systems

includes both the modeling and approximation of complicated terrains, as well as analysis of them (land area classification, construction planning, radar blockage, etc). For transportation systems, there are problems of route planning, traffic monitoring and flow optimization. This may involve making real time decisions based on remote sensing data, where the problem size is massive and solution efficiency is critical. Because of the inherent geometric constraints, geometry algorithms are often involved.

Mesh Generation

is used in finite element modeling in engineering structures and fluid (hydro or aero) dynamics (for example, wind tunnel simulations, weather forecasting, etc). The are many geometry aspects associated with the algorithms for constructing good modeling meshes in 2D (surface), 3D (volume), and higher dimensions. Special meshes are needed for studying shock waves and vortices in fluid flows.


needs geometry algorithms to solve robot motion planning problems. This involves both obstacle collision avoidance and minimal route planning (perhaps with other geometric constraints, like terrain slope). Problems involve geometry algorithms for moving polytope objects past polytope obstacles. The robots involved can be used for industrial purposes, or can be fully or semi autonomous vehicles. For example, autonomous robots we send to other planets will need to have computer vision for reconstructing scene geometry models which are then used for exploratory motion planning.

Manufacturing and Product Design

involves solid modeling using CAD/CAM systems that must adhere to spatial geometric constraints. Surface and volume design may include simple geometric primitives or more esoteric surfaces and shapes plus their layout in the product. Within the design models, engineering specifications need to be checked, and analysis (such as for stress or part failure) needs to be made using the design geometry.

Molecular Biology

has a high demand for geometry algorithms to model and analyze large scale molecular models associated with proteins, DNA, etc. The human genome project is producing more-and-more data every day, and using it to produce and investigate models of the basis of life and evolution is an enormous challenge. Even at the rudimentary level of cellular mechanisms, breakthroughs in geometric modeling and understanding may be the key to finding cures for genetic diseases (like cancer, Alzheimer's, etc). A specific promising problem is to model the spatial structure of proteins, and use this to design drugs that geometrically bind with their receptors.

These are some of the areas in which geometry algorithms play a critical role. Since everything we see and touch has a geometric aspect enabling us to understand our world, and computer graphics is gaining momentum, more-and-more areas of endeavor will start to be influenced by geometry algorithms. You will recognize them when you see them. But, will you know the best algorithms for new areas of application? Knowing the fundamentals, and the scope of our current knowledge will help.


© Copyright 2012 Dan Sunday, 2001 softSurfer