\+ \.Geometry in Action \- \# individual page titles \!align \.: Sequence Alignment \- \!arch \.: Architecture \- \!assembly \.: Assembly Planning \- \!astro \.: Astronomy \- \!bio \.: Biology \- \!cad \.: CAD \- \!cam \.: CAM \- \!carto \.: Cartography and Geographic Information Systems (GIS) \- \!char \.: Character recognition \- \!conf \.: Conferences \- \!constraint \.: Constraints \- \!control \.: Control Theory \- \!csg \.: CSG \- \!datamine \.: Data Mining \- \!delaunay \.: Delaunay Triangulation \- \!gdraw \.: Graph Drawing \- \!geom \.: Geometric References \- \!graphics \.: Graphics \- \!grasp \.: Grasping and Fixturing \- \!hull \.: Convex Hulls \- \!interpolate \.: Interpolation \- \!jour \.: Journals \- \!sci \.: Scientific Computation \- \!medial \.: Medial Axes \- \!medic \.: Medical Imaging \- \!meshgen \.: Mesh Generation \- \!metal \.: Metallurgy \- \!metro \.: Metrology \- \!molmod \.: Molecular Modeling \- \!mst \.: Minimum Spanning Trees \- \!patent \.: Patents \- \!quadtree \.: Quadtrees \- \!recent \.: Recent Additions \- \!relate \.: Related Pages \- \!robot \.: Motion Planning \- \!sigproc \.: Signal Processing \- \!soc \.: Sociology \- \!soil \.: Earth Sciences \- \!teach \.: Teaching Resources \- \!telecom \.: Telecommunication \- \!textile \.: Textile Layout \- \!timber \.: Timber Processing \- \!typography \.: Typography \- \!vidgames \.: Game Programming \- \!vision \.: Vision \- \!vlsi \.: VLSI \- \!voronoi \.: Voronoi Diagrams \- \!vreal \.: Virtual Reality \- \!window \.: Windowing Systems \- \+

Geometry in Action

\- \# blurbs and intros \!index This directory holds pages for Geometry in Action, a collection of various areas in which ideas from discrete and computational geometry (meaning mainly low-dimensional Euclidean geometry) meet some real world applications.

For the main entry point to this collection, go to http://www.ics.uci.edu/~eppstein/geom.html.

Files in this directory not pointed to directly from there: \- \!align

Biological Sequence Alignment

Sequence alignment is a problem of taking multiple sequences of characters, representing DNA sequences or proteins, and finding subsequences which match well with each other (according to some measure involving the lengths of the subsequences, the number and lengths of the gaps in them, etc). A common method of performing this is by finding small fragments that match (e.g. by exact string matching techniques) and then stringing the fragments together to form a longer alignment. By considering the positions of the fragments in each string to be coordinates in some Euclidean space, the problem becomes one amenable to orthogonal range searching techniques from computational geometry (and the decomposition of space formed by, for each point, determining the best previous point to chain it to, has strong resemblances to a rectilinear Voronoi diagram). Similar ideas also apply to a problem of comparing sequences of gene markers (where now the coordinates are positions of markers on a chromasome). \- \!arch

Architecture

The influence of computational geometry in architecture is mainly indirect but multifaceted, via computer graphics for architectural visualization, virtual reality for simulated walkthroughs, computer aided design, geographic information systems for land use planning, and finite element methods for structural simulation (see [Alexander, Black, and Tsutsui, "The Mary Rose Museum", Oxford 1995] for a nice example of a design informed by this last consideration). However it seems likely that within each of those areas, special problems arise in dealing with architectural information, and that more direct connections can also be made. \- \!assembly

Assembly Planning

This subarea of computer aided manufacturing involves automatically determining a sequence of motions to assemble a product from its individual parts. The motions can include part motions, grasping locations, tool access, fixture planning, factory layout, and many other issues, all of which have complex geometric components that use computational geometry techniques (or should). Most assembly planners have only considered a small subset of such issues.

Related areas: computer aided manufacturing, grasping and fixturing, robot motion planning. \- \!astro

Astronomy

Computational geometry problems arise in astronomy in observation planning, shape reconstruction for irregular bodies such as asteroids, clustering for galaxy distribution analysis, and hierarchical decomposition of point sets for n-body simulations. \- \!bio

Biology

\- \!cad

Computer Aided Design

Related areas: computer graphics, computer aided manufacturing, solid modeling, constraing solving, architecture, VLSI design. \- \!cam

Computer Aided Manufacturing

Computer aided manufacturing concerns the use of algorithms for planning and controlling fabrication processes. These algorithms are also important to computer aided design, since it is important to be able to test manufacturability as part of the design process. Specific areas of computer aided manufacturing listed as separate topics here include assembly planning, grasping and fixturing, metrology, robot motion planning, and textile layout. \- \!carto

Cartography and Geographic Information Systems

A geographic information system (GIS) is simply a database of information about natural and man-made geographic features such as roads, buildings, mountains... These systems can be used for making maps, but also for analyzing data e.g. for facility location. There has been some communication between the geometry and GIS communities (e.g. geographer Michael Goodchild gave an invited lecture on "Computational Geography" at the 11th ACM Symp. Comp. Geom.) but more could be done to bring them together. Geographic problems already visible in the geometry community include interpolation of surfaces from scattered data, overlaying planar subdivisions, hierarchical representations of terrain information, boundary simplification, lossy compression of elevation data (e.g. by using a piecewise linear approximation with few facets), and map labelling. Other interesting geometric issues include handling of approximate and inconsistent data, matching similar features from different databases, compression of large geographic databases, cooperation between raster and vector representations, visibility analysis, and generation of cartograms (maps with area distorted to represent other information such as population).

A particularly important geometric data structure in geographic analysis is the Voronoi diagram, which has been used for to identify regions of influence of clans and other population centers, model plant and animal competition, piece together satellite photographs, estimate ore reserves, perform marketing analysis, and estimate rainfall. \- \!char

Character recognition

\- \!conf

Computational geometry conferences and workshops:

Algorithms and combinatorics conferences:

Conferences from geometric application areas:

\- \!hull

Convex Hulls

\- \!constraint

Constraint Solving

More a technique than an application, geometric constraint solving consists of finding configurations of points, lines, circles, and other geometric figures constrained to have certain relations to each other. This sort of problem finds applications in a number of areas including computer aided design, molecular modeling, and robot motion planning. \- \!control

Control Theory

\- \!csg

Constructive Solid Geometry and Solid Modeling

Geometric questions related to solid modeling include conversion between different representations including boundary nets, constructive solid geometry (representations involving Boolean combinations of simple base shapes), and hierarchical decomposition; combination (such as intersection and union) of shapes; blending surfaces; and data structures for graphical rendering of models. More could be done to connect the models used in computational geometry (typically polyhedra) with those in computer aided design (typically involving splines or other higher order curves and surfaces). \- \!datamine

Data Mining and Multidimensional Analysis

Data mining is the process of querying large databases (such as point-of-sale records) with the aim of distilling from them broad patterns and smaller collections of useful information. There seems to be little work in this area from the computational geometry perspective, but there are likely good geometric problems to be found in it. One such problem is coping with high-dimensional data, by condensing information down to a small number of relevant dimensions and applying geometric clustering techniques. Any algorithm to be used in this context must be fast, but it is perhaps more important to deal with amounts of data that do not fit in memory, and keep to a minimum the total number of I/O operations needed, as has been considered in recent work of Goodrich et al. ("External-memory computational geometry", 34th FOCS, 1993, 714-723). There are also interesting connections with geographic information systems, which face similar problems of querying large databases with more explicitly geometric content. \- \!gdraw

Graph Drawing

Graph drawing can be thought of as a form of data visualization, but unlike most other types of visualization the information to be visualized is purely combinatorial, consisting of edges connecting a set of vertices. Applications of graph drawing include genealogy, cartography (subway maps form one of the standard examples of a graph drawing), sociology, software engineering (visualization of connections between program modules), VLSI design, and visualization of hypertext links. Typical concerns of graph drawing algorithms are the area needed to draw a graph, the types of edges (straight lines or bent), the number of edge crossings for nonplanar graphs, separation of vertices and edges so they can be distinguished visually, and preservation of properties such as symmetry and distance. The area has a large literature, concentrated in the annual Graph Drawing symposia, and I won't try to link here to all available research projects and papers on the subject, only those with some particular historical or application interest. \- \!geom

General Geometric References

\- \!graphics

Graphics

This area is quite closely connected with computational geometry; for instance ACM TOG often publishes computational geometry papers. Geometric research topics in graphics include data structures for ray tracing, clipping, and radiosity; hidden surface elimination algorithms; automatic simplification for distant objects; morphing; clustering for color quantization; converting triangulated surfaces to strips of triangles (some graphics engines take inputs in this form to save bandwidth); and construction of low-discrepancy point sets (for oversampling to eliminate Moire effects in ray tracing). Specialized applications of graphics in which other geometric ideas are needed include architecture, virtual reality, and video game programming. This area is also related to mesh generation in several ways: both fields use triangulation algorithms to partition complex surfaces into simpler pieces, and radiosity calculations in graphics are essentially a special case of the finite element method. \- \!grasp

Grasping and Fixturing

Although one version of this problem comes from robotics and the other comes from manufacturing, the aim of both is the same: to construct a placement of obstacles (robot fingers or fixtures) preventing the movement of some part. \- \!interpolate

Interpolation and Extrapolation

In many areas ranging from cartography to molecular imaging and modeling, one finds the need to fit a function or surface to a collection of scattered data points. Interpolation refers to finding values for points between the given points (i.e. inside their convex hull); if the function should extend over a wider region of the input domain the problem is instead referred to as extrapolation. The method chosen should depend on the properties one desires the resulting surface to have; many interpolation methods are based on Voronoi diagrams and Delaunay triangulations. A piecewise constant approximation, used in rainfall estimation, can be found by simply choosing the function value in each Voronoi cell to be that of the cell's generating site. This is a analog for continuous domains of the nearest neighbor rule from machine learning theory, which has been generalized e.g. to voting among three nearest neighbors; one could similarly define median-of-three interpolation schemes (still piecewise constant, but less susceptable to erroneous data), however I know of no application in which such schemes have been tried. The Delaunay triangulation itself provides a piecewise linear continuous function, defined within the convex hull of the input, that minimizes a certain energy functional. "Natural neighbor interpolation" is defined for each point x by adding x as a site to the Voronoi diagram of the original sites, and averaging the sites' values weighted by the fraction of the cell for x previously covered by each other cell. This somewhat complicated procedure results in a continuous function smooth everywhere except at the original sites. At the 1995 ARO-MSI Worksh. on Comp. Geom., Ken Clarkson described a similar technique that results in a function smooth everywhere. \- \!jour

Computational geometry journals:

Algorithm, discrete math, and general geometry journals:

Journals from geometric application areas:

\- \!medic

Medical Imaging

A key problem in medical computation is reconstruction of shapes (of organs, bones, tumors etc) from lower dimensional information such as CAT scans and sonograms. The CAT scan information is originally one-dimensional, but is transformed into two-dimensional slices by signal processing techniques. However the reconstruction of three-dimensional shapes from slices becomes a more geometric problem, which can be abstracted as that of finding a surface connecting a collection of contour lines or data points. A different problem relates to compression of medical images for transmission and storage; this differs from most other applications of image compression in that little or no loss of information can be tolerated. \- \!meshgen

Mesh Generation

A key step of the finite element method for numerical computation is mesh generation. One is given a domain (such as a polygon or polyhedron; more realistic versions of the problem allow curved domain boundaries) and must partition it into simple "elements" meeting in well-defined ways. There should be few elements, but some portions of the domain may need small elements so that the computation is more accurate there. All elements should be "well shaped" (which means different things in different situations, but generally involves bounds on the angles or aspect ratio of the elements). One distinguishes "structured" and "unstructured" meshes by the way the elements meet; a structured mesh is one in which the elements have the topology of a regular grid. Structured meshes are typically easier to compute with (saving a constant factor in runtime) but may require more elements or worse-shaped elements. Unstructured meshes are often computed using quadtrees, or by Delaunay triangulation of point sets; however there are quite varied approaches for selecting the points to be triangulated.

There has now been considerable theoretical work in the geometry community on these problems, complementing and building on practical work in the numerical community. There is also beginning to be a convergence of these communities, in which theoretical work is fed back in to practical mesh generation applications. Theoretically, the preferred type of mesh is the triangulation or simplicial complex, but in mesh generation practice quadrilaterals or higher dimensional cubical element shapes are preferred (both because fewer are typically needed and because they have better numerical properties). Remaining problem areas in the theory of meshing include triangulations in dimensions higher than two, meshes with cubical elements, mesh smoothing, mesh decimation and multigrid methods, and data structures for efficient implementation of meshing algorithms. There has also been some theoretical work on using geometry to partition meshes by finding small separators of their underlying graphs.

The list of pointers here is not intended to be comprehensive; see Robert Schneiders' page for more pointers. I have tried to include a mixture of research groups working on theoretical problems with commercial packages and the issues they raise. \- \!metal

Metallurgy

\- \!metro

Metrology

Metrology is the science of measurement of objects at all scales. The NIST's project on "Computational Geometry and Metrology" includes the use of geometric techniques including mesh generation in computer simulations to study the accuracy and precision of coordinate measuring machines (machines which measure the dimensions of parts in a three-dimensional coordinate system). There are also connections with geographic information systems relating to problems of surveying or otherwise measuring large areas of land.

One type of problem of particular interest in manufacturing is determining from a sequence of measurements the tolerance of a part; that is, its departure from the Platonic ideal form of its design. There has been some related work in the computational geometry community, on problems such as constructing the minimum width annulus containing the boundary of an input figure (a measure of its roundness) however there has been little systematic treatment of such problems. Chee Yap recently spoke on this subject at the 5th MSI Worksh. on Computational Geometry; his talk pointed out the possibility of designing algorithms that take advantage of some known structure in a sequence of measurements, and of coupling measurement and computation in an adaptive probing algorithm. \- \!mst

Minimum Spanning Trees

\- \!molmod

Molecular Modeling

Connections have been growing recently between the molecular modeling community and the computational geometry. Many questions in molecular modeling can be understood geometrically in terms of arrangements of spheres in three dimensions. Problems include computing properties of such arrangements such as their volume and topology, testing intersections and collisions between molecules, finding offset surfaces (related to questions of accessability of molecule subregions to solvents such as water), data structures for computing interatomic forces and performing molecular dynamics simulations, and computer graphics algorithms for rendering molecular models accurately and efficiently (taking advantage of their special geometric structure). Classical molecular modeling has dealt with biological molecules which generally have a tree-like structure, but applications to nanotechnology require dealing with more complicated diamond-like structures; it is unclear to what extent this affects the relevant algorithms. \- \!patent

Patented Applications of Computational Geometry

Some of the following patents are applications of geometric algorithms, while others appear to patent the algorithms themselves. Presumably I have missed many more than I have found. \# Terms searched: \# convex hull (several hits) \# quadtree (several hits) [only 1995-present searched] \# voronoi (several hits) \# zonohedron (a couple hits) \# unsuccessful searches: \# euclidean (many hits, few relevant) \# chazelle, dobkin, edelsbrunner, guibas (some hits but not good ones) \# delaunay (a couple hits nonoverlapping w/voronoi, \# but most involved other people named Delaunay) \# medial axis (several hits, more than half nonoverlapping w/voronoi, \# but all just referred to centerlines of objects) \# binary space partition (no hits but see patent 3889107) \# segment tree (no hits) \# interval tree (no hits) \# spanning tree (many false hits) \# trapezoid (many false hits) \- \!quadtree

Quadtrees and Hierarchical Space Decomposition

The basic principle of a quadtree is to cover a planar region of interest by a square, then recursively partition squares into smaller squares until each square contains a suitably uniform subset of the input; for instance this can be used to compress bitmap images by subdividing until each square has the same color value. This and related partitions have many applications in computational geometry and geometric applications, including data clustering, shape representation, n-body simulation in astronomy and molecular modeling, and mesh generation. \- \!recent

Recent Additions

These files and pointers have been added to "Geometry in Action" or modified since 2004. \- \!relate

Related "Applications Of..." Pages

\- \!robot

Robot Motion Planning

The study of exact algorithms for robot motion planning forms a major subarea of computational geometry, with connections also to symbolic and algebraic computation. Note that motion planning is useful not only for computer control of actual robots; in his invited talk at FOCS 1995, Jean-Claude Latombe showed impressive videos of applications of the same techniques in assembly planning and to computer animation. \- \!sci

Scientific Computation

Computation and simulation has rapidly become a third branch of science, standing next to the older branches of theory and experiment. Much scientific computation is done with the finite element method or related techniques, requiring a geometric mesh generation stage to set up the computation, and often involving more geometry in finding sparse decompositions of the resulting matrices. Other scientific problems involve more directly the geometry of polyhedra or local neighbor interactions. We include separate sections for astronomy, biology, earth sciences, and molecular modeling. \- \!sigproc

Signal Processing

Digital image compression and transmission is a problem that (with the growth of the world wide web) is rapidly growing in prominence, and may be a fertile source of links between geometry and signal processing. One example is a recent note in the 11th ACM Symp. Comp. Geom., in Schwarz et al. describe a fast algorithm for finding the minimum area parallelogram enclosing a given polygon, motivated by a problem in signal processing of compressing image data via "rational decimation systems". \- \!soc

Sociology and Social Network Theory

Social network theorists study the interactions of individuals and groups by analyzing the pattern of their connections. These patterns can typically be represented as graphs; graph drawing provides an important way of understanding these graphs. \- \!soil

Earth Sciences

\- \!teach

Geometry Courses and Teaching Materials

Computational geometry textbooks:

Computational geometry courses:

Courses and course material from geometric applications: \- \!telecom

Telecommunication

\- \!textile

Textile Layout

The problem here is, given a pattern in the form of a collection of shapes (polygons), to arrange the shapes so they can be cut from a piece of fabric with as little wasted fabric as possible. Essentially this is a two-dimensional bin-packing problem with various complications: the width of the fabric is fixed and one intends to minimize length; the shapes can sometimes be placed only in a small number of possible orientations so that the fabric pattern lines up correctly; the shapes can be quite far from convex; and (for leather) the hides out of which the shapes must be cut can be quite variable in shape and quality. This area is also related to more tractible geometric problems such as testing whether one polygon can be translated to fit inside another. Textile layout has some visibility in the geometry community largely due to the efforts of Victor Milenkovic, now at the University of Miami. \- \!timber

Timber processing

\- \!typography

Typography

Most fonts are represented these days digitally, as collections of spline curves, together with extra information representing kerning (intercharacter spacing) and "hints" for low-resolution rasterization. Although there does not seem to be a direct connection with the computational geometry community, there are a number of problems that could be addressed here: how to automatically choose spline curves to match a given drawing, how to kern and hint automatically or semi-automatically instead of by eye, and how to use geometric font characteristics to perform intelligent font substitution. There are also interesting computational issues connected with text layout (e.g. Knuth's line breaking algorithm in TeX) but these seem less geometrical. \- \!vidgames

Video and Computer Game Programming

Video game programming is closely related to computer graphics, but has its own special needs -- often speed is much more important than verisimilitude. Therefore rather than using slow but accurate graphics techniques such as radiosity, video game engines are typically based on simpler techniques such as raycasting, using binary space partitions as a primary geometric data structure. Simulation of non-player-characters in video games often requires some geometric computation, for instance of short paths around obstacles. There may also be the possibility of a connection with graph drawing, for automated layout of adventure game maps. \- \!vision

Vision

Many computer vision papers tend to apply signal processing techniques rather than discrete geometry, to be very heuristic, or to simply describe coordinate systems or other geometric modelling tools. However there has been some work in the computational geometry community on exact solution of geometric pattern matching problems associated with vision, for instance by Dan Huttenlocher's group at Cornell. Several vision projects use Voronoi diagrams to represent the structure of the image under study. \- \!vlsi

VLSI Design

VLSI circuit design involves many levels of abstraction; the most geometric of these is the physical design level, in which circuits are represented as (typically) collections of rectangles representing layers of various materials on a chip. Most of the layout, routing, and verification problems at this level involve some amount of computational geometry. At another level of abstraction, simulation of the electronic and physical properties of a chip involves interesting questions of mesh generation, in which there may be some advantage to be taken from the fact that the geometry is rectilinear and planar or nearly planar. \- \!voronoi

Voronoi Diagrams

The Voronoi diagram of a collection of geometric objects is a partition of space into cells, each of which consists of the points closer to one particular object than to any others. These diagrams, their boundaries (medial axes) and their duals (Delaunay triangulations) have been reinvented, given different names, generalized, studied, and applied many times over in many different fields. Voronoi diagrams tend to be involved in situations where a space should be partitioned into "spheres of influence", including models of crystal and cell growth as well as protein molecule volume analysis. \- \!delaunay

Delaunay Triangulation

The Delaunay triangulation of a point set is a collection of edges satisfying an "empty circle" property: for each edge we can find a circle containing the edge's endpoints but not containing any other points. These diagrams their and their duals (Voronoi diagrams and medial axes)) have been reinvented, given different names, generalized, studied, and applied many times over in many different fields. The Delaunay triangulation is also closely related by the so-called "lifting transformation" to convex hulls in one higher dimension. Many common methods for function interpolation and mesh generation are based in some way on Delaunay triangulations, but there are also many other ways in which this structure has been applied. \- \!medial

Medial Axes

The medial axis of a polygon is the boundary of the Voronoi diagram of its edges, and forms a tree-like skeleton useful in character recognition, road network detection in geographic information systems, and other applications. \- \!vreal

Virtual Reality

This is to a large extent a branch of graphics, with the focus on generation of real-time three-dimensional views of dynamic scenes. This is similar to video game programming but with a greater emphasis on accurate rendering and physical modeling. Problems of interest here include simplification of objects (to save time by avoiding the rendering of sub-pixel details) and collision detection. There are also connections with graph drawing for construction of 3d virtual environments that represent combinatorial structures. \- \!window

Windowing Systems and User Interface Programming

The rectangular geometry of most windowing user interfaces lends itself naturally to the orthogonal range searching techniques studied in computational geometry. A typical problem arising in this context might be to find a data structure for quickly determining which window or window system object is topmost at a given screen pixel (for instance this information is needed to process mouse clicks and to set the mouse's appearance). Range searching techniques can be useful even within a single window, to speed up scrolling and redisplay by determining which objects are visible in a region. In my own programming experience, I have used (a simplified implementation of) interval trees to greatly speed up scrolling in code for displaying large family trees. \- \# the entries themselves \+