\
\# 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 lowdimensional Euclidean
geometry) meet some real world applications.
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
\
3d recon
\!medic
 3d
reconstruction home page, NASA Ames Biocomputation Center.
\
3d shape
\!vision
\!voronoi
 3d shape and surface matching. Elias Kalaitzis of Edinburgh
uses 3d Voronoi diagrams in an iterated parallel procedure for
approximating a geometric transformation aligning a pair of shapes.
\
academic
\!cad
\!vlsi
 Academic
CAD sites on the web (primarily VLSI rather than other kinds of CAD).
\
acm
\!relate
 ACM's
SIGACT Long Range Planning Committee has prepared a list of
Contributions of Theoretical Computer Science.
\
acm int
\!carto
 ACM Int. Worksh. Advances in Geographic Information Systems.
3rd Worksh., Baltimore, Dec. 1995, call for papers.
4th Worksh., Rockville, MD, Nov. 1996,
call for papers.
\
acm special
\!graphics
 ACM Special Interest Group on
Graphics (SIGGRAPH).
\
acm trans
\!graphics
\!jour
 ACM Transactions on Graphics.
\
adaptive discretization
\#graphics
\#meshgen
\# lalonde not found 28 Aug 1998
 An
Adaptive Discretization Method for Progressive Radiosity,
P. Lalonde, UBC.
\
advanced school
\#conf
\#carto
\# no such host 22 May 2000

Advanced School on Spatial Data Handling, Venice, 1994.
\
agricultural
\!carto
\!quadtree
 The
Agricultural NonPoint Source Pollution Model claims to be using
Voronoi diagrams as a basis for spatial subdivision, but appears to
actually be using quadtrees.
\
aisee
\!gdraw
 aiSee graph
visualization software.
\
algorithmic foundations
\#conf
\#carto
\# 404 22 May 2000
 Algorithmic Foundations of
Geographic Information Systems, Int. Works. and Summer School,
Udine, Italy, Sept. 1996.
\
algorithms for fin
\!molmod
 Algorithms for finding the axis of a helix, J. Christopher, R. Swanson, and T. Baldwin.
The authors use this problem to detect structural patterns in protein
molecules.
\
algorithms for min
\!textile
 Algorithms for Minimizing Overlap of Translating Polygons,
Victor Milenkovic, 5th MSI Worksh. Comp. Geom.
\
alpha shapes
\!molmod
\!csg
 Alpha
shapes, defined by H. Edelsbrunner and others at U. Illinois,
provide a useful algorithmic tool for modeling shapes,
especially those formed by unions of spheres.
\
analysis
\!medic
\!medial
 Analysis of
metaphase chromosomes. D. Sudar et al. use medial axes to map
locations along images of chromosome structures.
\
anatomical
\!medic
 Anatomical modeling research, Rick Miranda, Colorado State.
Miranda's part in this study is finding optimal triangulations
to reconstruct surfaces by joining parallel contours.
\
annot
\!graphics
\!csg
 Annotated bibliography on object representation schemes for 3d graphics, H.G. Park, Air Force Inst. Tech.
\
annotated bib
\!medic
 Annotated bibliography on medical imaging, H.G. Park, Air Force Inst. Tech.
\
annotated bib
\!char
 Annotated
bibliography in online character recognition, J. R. Ward.
\
application
\!relate
 Application Challenges to Computational Geometry,
report of the Computational Geometry Impact Task Force
convened by B. Chazelle.
See also some
discussion
of the report (as well as related links) on Jeff Erickson's web page.
\
applications of 3d dt
\!soil
\!carto
\!delaunay

Applications of 3d Delaunay triangulation algorithms in geoscientific modeling, R. Lattuada and J. Raper.
Uses 3d DT for shape reconstruction of 3d geographic objects such as aquifers, ocean currents, and weather fronts.
\
applications of cg
\!vlsi
\!interpolate
\!mst
 Applications of computational geometry.
John Hershberger describes some geometric problems arising in his work
at Mentor graphics including interpolation of thermal data, minimum spanning trees, and breakout
routing in PC board design.
\
applications of cg
\!vreal
\!carto
 Applications of computational geometry: virtual reality, 3d graphics, and route planning. Abstract for a talk in which Joe Mitchell describes his ongoing work.
\
applications of linear
\!astro
\!quadtree
 Applications
of the linear quadtree to astronomical databases, P. Barrett, NASA.
Encoding astronomical coordinates with quadtrees can provide significant
improvements in efficiency when accessing sources near a given direction
and can aid in the correlation of positions from different astronomical
catalogs.
\
applications of vor
\!voronoi
\!bio
 Applications
of Voronoi Tesselations to Tumour Cell Diagnosis, Lynne Dunckley.
\
arrythmia classification
\#delaunay
\#interpolate
 Arrhythmia classification.
D. Cubanski and D. Cyganski use tendimensional Delaunaybased
interpolation methods to detect heart rhythm disorders from electrocardiograms.
\
aspects
\!metro
 Aspects of Dimensional Tolerancing,
Chee Yap, 5th MSI Worksh. Comp. Geom.
\
assembly
\#assembly
 Assembly sequence planning bibliography, J. Wolter, Texas A&M U.
\
atlas
\!gdraw
 Atlas of science.
G. Edgar describes this project in which the publishers of Science
Citation Index use graph drawing techniques to clarify the relations
between different research specialties.
\
automated
\!voronoi
\!carto
 Automated derivation of high accuracy road centrelines:
Thiessen polygons technique. A. Ladak and R. B. Martinez use
Voronoi diagrams to automatically construct maps of the roads in Qatar
from databases of nearby buildings.
\
automation
\#assembly
\#grasp
 Automation of assembly operations on parts,
J. P. Baartman, T. U. Delft.
Includes also sections on grip planning.
\
basic theoretic
\!vidgames
 For basic theoretical work on BSP trees, see two
papers by F. Yao and M. S. Paterson: "Efficient binary space
partitions for hiddensurface removal and solid modeling", 5th
Symp. Comp. Geom. (1989) 2332 and Disc. Comp. Geom. 5 (1990)
485503. and "Optimal binary space partitions for orthogonal
objects", 1st SODA (1990) 99113. See also E. Torres,
"Optimization of the binary space partition algorithm (BSP) for the
visualization of dynamic scenes", Eurographics (1990) 507518, and
Agarwal et al., "Binary space partitions for fat rectangles, 37th FOCS (1996).
Apparently the question of tight complexity bounds for planar
BSP trees remains open.
\
biblio
\!graphics
 Bibliographies on Computer Graphics, AlfChristian Achilles, U. Karlsruhe.
\
bibtex
\!meshgen
 BibTeX references from "Mesh
generation and optimal triangulation" (survey by M. Bern and D.
Eppstein in "Computing and Euclidean
Geometry", World Scientific 1992 & 1995).
\
brlcad
\!csg

BRLCAD CSG system, Army Research Lab.
\
bsp tree
\!vidgames
 The BSP tree FAQ is largely devoted to implementation issues,
and includes a description of BSP usage in DOOM.
\
cancer
\!bio
\!mst
 Cancer
imaging. The BC Cancer Research Ctr. uses minimum spanning trees to
describe the arrangements of nuclei in skin cells.
\
carafe
\!vlsi
 Carafe  An
Inductive Fault Analysis Tool for CMOS VLSI Circuits. This VLSI
layout checker finds circuit breaks using a plane sweep
algorithm.
\
carlo
\!arch
 Biagio di Carlo,
geodesic architect.
\
cartography resources
\!carto
 Cartography
resources on the web, Jeremy Crampton, George Mason U.
\
case studies
\!carto
\!bio
\!voronoi
\!datamine

Case Studies in Biometry. This book by N. Lange and others
mentions Voronoi diagrams as a method for detecting clusters
of disease incidence.
\
castalia
\!astro
\!hull
 Castalia and
Deimos.
Philip Stook at U. Western Ontario
mentions an application of 3d convex hulls in mapping the surfaces
of these two asteroids.
\
cell
\!bio
 Cell
aggregation and sphere packing.
\
central path
\!medial
\!medic
\!vreal
 Central path
algorithm. Y.R. Ge and D. Stelts use medial axes to find paths
along the central line of the intestinal system as part of a
virtual endoscopy system
for noninvasive medical diagnosis.
\
centre for research in geomatics
\!carto
 Centre for Research in Geomatics, U. Laval.
\
cerebellar
\!bio
 Cerebellar flat mapping.
Describes the use of circlepacking methods to map the convoluted
surface of the brain into a Euclidean or hyperbolic plane to help
visualize its functional areas.
See also M.
Hurdal's web page on the same research.
\
chaining
\!align
 Chaining MultipleAlignment Fragments in SubQuadratic Time,
G. Myers and W. Miller, U. Arizona,
from SODA '95.
\
chee yap's report
\!cam
 Chee
Yap's report from the NSF Workshop on Manufacturing and
Computational Geometry, held April 1994 at NYU.
\
chemists art
\!molmod
 Chemist's
http://www.csc.fi/lul/chem/graphics.html
Art Gallery. Molecular visualization pointers from L. Laaksonen,
Center for Scientific Computation, Finland.
\
cmu algorithms
\!relate
 CMU CS 15850(C): Algorithms in the Real World.
Course offered by G. Blelloch, G. Miller, and D. Sleator.
\
cmu digital
\!carto
 CMU
Digital Mapping Laboratory.
\
cmu fixture
\!grasp

The CMU fixture design and analysis tool
for testing the suitability of proposed fixtures.
\
collision
\!robot
\!vreal
 Collision
detection research at UNC.
\
committee
\!relate
 The Committee
for the Advancement of Discrete and
Combinatorial Mathematics is collecting
a list of
applications of discrete math
and
wants your help.
\
commun acm theme section
\!jour
\!carto

Commun. ACM Theme Section: Geographic Information Systems,
S. Shekhar and M. Egenhofer, eds., call for papers.
\
comp.fonts
\!typography
 The comp.fonts
Home Page
\
computable city
\!arch
 The
Computable City. M. Batty views urban growth through the lens of
the computer. With many pointers to related work.
\
computational geometry based
\!telecom
 A
computationalgeometrybased tool for the cellular design of milimeter
wave mobile communications systems in urban environments, Velez and
Brazio, 1st CGC Worksh. Computational Geometry.
(Something may be wrong with this file  it comes up blank for me in
Ghostview.)
\
computational geometry mail
\!geom
 Computational geometry mailing lists
and threaded archive.
\
computational geometry problems in integrated
\!vlsi
\!index
 Computational Geometry Problems in
Integrated Circuit Design and Layout.
Notes by D. Eppstein from a lecture by V. T. Rajan.
\
computational geometry soft
\!geom
 Computational geometry software collections:
CGAL.
Nina Amenta, Geometry Ctr..
Jeff Erickson, UIUC.
Seth Teller, MIT.
J. Richard Bradley and Steven S. Skiena, SUNY Stony Brook.
Dan Sunday, GeometryAlgorithms.com.
\
computational physics
\!sci
 Computational
physics meets computational geometry, Glimm et al, 1st CGC
Worksh. Computational Geometry. The authors use combinatorial
geometry to represent discontinuities in problems of
fluid dynamics, elastic and plastic deformation, semiconductor manufacture,
and percolation.
\
computational topology
\!geom
\!carto
\!vision
\!cad
\!meshgen
\!graphics
\!molmod
\!index
 Computational Topology.
Survey paper by Dey, Edelsbrunner, and Guha, presented at the conference
"Computational Geometry  Ten Years After". Includes descriptions of
applications in image processing, cartography, graphics, solid modeling,
mesh generation, and molecular modeling.
\
computer aided
\!jour
\!cad
 Computer Aided Geometric Design.
\
computer aided geom
\!jour
\!medic
\!index
 Computer Aided Geometric Design, special
issue on Medical Visualization, call for papers. Deadline is Jan 31, 1997.
\
computer aided geom
\!cad

Computer aided geometric design at Leeds U.,
including work on ship and aircraft shapes.
\
computer graphics dir
\!graphics
 Computer Graphics
directory, Perceptual Science Lab, UC Santa Cruz.
\
computer science
\!astro
 Computer science and astrophysics, R. Anderson.
\
computer vision
\!vision
 Computer Vision home page (CMU).
\
constructive solid geometry bib
\!csg
 Constructive solid geometry bibliography,
Ian Grimstead, U. Wales.
\
converting
\!graphics
 Converting
sets of triangles with shared edges into triangle strips,
Brad Grantham.
\
convex hull
\!voronoi
\!delaunay
\!hull
\!medial
 Convex hull,
Voronoi diagram, and Delaunay triangulation software
from
Nina Amenta's CG software directory.
\
convex hulls
\!hull
\!interpolate
\!voronoi
 Convex hulls and interpolation. Ken Clarkson describes some implementation
details of algorithms for convex hulls, alpha shapes, Voronoi diagrams,
and natural
neighbor interpolation.
\
cosmology
\!astro
\!mst
 Cosmology at
the University of Kentucky. This group works on largescale
structure formation, using methods including Nbody simulations and
minimum spanning trees.
\
cse690
\!gdraw
\!teach
 CSE690: Graph Drawing Seminar, Auburn U.
\
cubit
\!meshgen
 The
CUBIT hexahedral mesh generation project at Sandia Labs
(and another web
page about CUBIT).
\
current
\!vreal
 Current
research in simulation and virtual environments, B. Mirtich, Berkeley.
\
curves
\!cad
 Curves
and surfaces for geometric modeling, and
Geometric Methods and Applications for Computer Science and Engineering, reviews and supplementary material for two books by
Jean Gallier.
See also his courses
CIS 610 and
CIS 700 based on the second book.
\
cutting
\!textile
 Cutting
fabric for sails, Eugene Popov.
\
darren knight
\!arch
\!meshgen
 Darren Knight Gallery. Mesh generation meets architectural design.
\
data collection
\!astro
 Data
Collection for the Sloan Digital Sky Survey  A Network Flow Heuristic,
Robert Lupton, F. Miller Maley, and Neal E. Young, SODA '96, describes a
planar clustering problem
arising in planning the telescope positions for a sky survey,
and gives a heuristic solution.
\
data format
\!carto
\!index
 Data formats for addresses.
James Guthrie discusses the complexities of naming systems in GIS's
and the difficulty of associating names to geographic/geometric entities.
\
data foundation
\!carto
 A
data foundation for the national spatial data infrastructure, US
Natl. Research Council, 1995.
\
data mining
\!datamine
 Data
mining research at Los Alamos.
\
davinci
\!gdraw
 da Vinci graph visualization system, M. Fröhlich, U. Bremen.
\
decomposing
\!csg
\!voronoi
 Decomposing
trimmed surfaces using the Voronoi tesselation, P.Y. Tsai and B.
Hamann, Mississippi State U.
\
delaunay and voronoi
\#delaunay
\#voronoi
\# natk now http://wwwlifia.info.unlp.edu.ar/~natk/ but grumont2 gone,
\# 4 Sep 1998
 Delaunay
and Voronoi helps trucks and salesman (abstract). Krasnogor et al
use Voronoi diagrams and Delaunay triangulations to help solve vehicle
routing problems.
\
delaunay interp
\!delaunay
\!interpolate
\!index
 Delaunay interpolation.
Various people discuss the pros and cons of using Delaunay triangulation
for data interpolatation.
\
delaunay refinement
\!delaunay
\!meshgen
 A Delaunay refinement algorithm for quality
2dimensional mesh generation, Jim Ruppert, NASA.
\
delaunay triangulations in two
\!delaunay
 Delaunay triangulations in two and three dimensions.
Master thesis by Jörg Krämer
lists applications including crystal growth, metallurgy, cartography,
mesh generation, stereolithography, and visualization.
\
delorme
\#carto
\# 404 22 May 2000
 DeLorme Mapping's
collection of geographyrelated web sites.
\
dept spatial
\!carto
 Dept. Spatial Information Science and Engineering, U. Maine.
\
der technik
\!voronoi
\!carto
 Der
Technik hinter dem Mühlentag (in German).
Kasper Schiess uses Voronoi diagrams to set up web page image maps
of geographical locations
in such a way that clicking on any point in the map leads to a description
of the nearest location.
\
designing
\!sigproc
 Designing
twodimensional filter banks based on geometric decompositions of the
frequency domain,
W. Chen and E. Lee, Berkeley.
\
detail
\!meshgen
\!medial
\!vreal
\# not responding 28 Aug 1998
 Detail removal.
The Queen's U. finite element group uses medial axes to simplify parts
to be simulated while maintaining as little error as possible,
as part of their
QUB mesh
generation system.
Presumably similar ideas would also apply to model simplification
for virtual reality.
\
detecting actin
\!bio
\!vision
\!mst
 Detecting actin fibers in cell images.
A. E. Johnson and
R. E. ValdesPerez use minimum spanning trees for biomedical image analysis.
\
dieopen
\!cam
 Dieopen
direction.
Dave Wuerger discusses algorithms for a geometric problem in "the
design of dies for nearnetshape manufacturing processes".
See also followon work by Georg Kurth.
\
digital design media
\!teach
\!cad

Digital Design Media online textbook.
\
dimacs
\!conf
\!molmod
 DIMACS
Worksh. on Geometrical Methods for Conformational Modeling,
Aug. 1995. Program and talk abstracts.
\
directory of assembly
\#assembly
 Directory
of Assembly Planning Research, Sandia Labs.
\
dirichlet
\!bio
\!voronoi
 Dirichlet
tessellation of bark beetle spatial attack points. J. Byers uses Voronoi diagrams to understand the spatial distribution of insects.
\
discrete
\!bio
\!molmod
 Discrete
algorithms in biology and chemistry (in German). Molecular modeling
and related projects at the German Nat. Res. Ctr. for Inf. Tech.,
Inst. for Algorithms and Scientific Computing.
\
displaying
\!quadtree
\!graphics
 Displaying a VoxelBased Object Via Linear Octrees, Gargantini et al., Proc.
SPIE 1986.
\
dod groundwater
\!carto
\!soil
\!interpolate
\# no such host 22 May 2000  current GMS pages at BYU dont seem to have this
 The
DoD groundwater modeling system uses
natural neighbor interpolation for groundwater plume characterization.
\
drawing smooth curves
\#interpolate
 Drawing
smooth curves through corner cutting. An automatic method of
smoothing interpolating curves or surfaces by repeated truncation,
implemented in Java by Peter Schröder.
\
dynamic scene
\!graphics
\!meshgen
 Dynamic
Scene Radiosity.
Robert Grzeszczuk, U. Chicago, maintains a triangulated mesh
dynamically, keeping track of the topological changes in
the pattern of shadow crossings in an image.
\
dynamic seg
\!carto
\!voronoi
 Dynamic segmentation and Thiessen polygons: a solution
to the river mile problem.
Hargrove, Winterfield and Levine use Voronoi diagrams to
construct a coordinate system for locations on water or along
other linear structures such as interstate highways.
\
dynamic weighted
\!delaunay
\!soil
 Dynamic Weighted
Delaunay Triangulations for Efficient Collision
Detection in Distinct Element Modeling and
Simulation of Granular Media,
JeanAlbert Ferrez, EPFL.
\
efficient alg
\!csg
 An
efficient algorithm for finding the CSG representation of a simple
polygon, D. Dobkin, L. Guibas, J. Hershberger, and J. Snoeyink, DEC
SRC, 1989.
\
efficient data
\!datamine
\!recent
\# 7 Mar 2005
 Efficient data reduction with EASE and Deterministic sampling beyond EASE. Hervé Brönnimann and colleagues apply deterministic sampling techniques from computational geometry to data mining in largescale data streams.
\
efficient geometric alg
\!cam

Efficient geometric algorithms for workpiece orientation in 4 and
5axis NCmachining, Prosenjit Gupta, Ravi Janardan, Jayanth
Majhi, and Tony Woo, 5th MSI Worksh. Comp. Geom.
\
ehrhart
\!compiler
 Ehrhart
polynomials for parallel programs. This project at Strasbourg
computes various quantities used by an optimizing
parallel compiler by counting points in polyhedra.
\
electronic primer
\!constraint
 An
Electronic Primer on Geometric Constraint Solving,
Christoph Hoffmann, Purdue.
\
euclidean
\!mst
\!sci
 The
Euclidean minimum spanning tree mixing model. S. Subramaniam and
S. B. Pope use geometric minimum spanning trees to model locality of
particle interactions in turbulent fluid flows. The tree structure of
the MST permits a lineartime solution of the resulting
particleinteraction matrix.
\
eurographics
\!vreal
\!conf
 7th
Int. Eurographics Worksh. Computer Animation and Simulation, 1996,
proceedings contents, abstracts, and demos.
\
exact comp
\!metro
 Exact Computational Geometry and Tolerancing Metrology,
survey by Chee Yap, NYU, Feb. 1995
\
external
\!carto
 Externalmemory
algorithms with applications in geographic information systems,
L. Arge, Duke.
\
extracting features
\!carto
\!vision
\!mst
 Extracting features from remotely sensed images. Mark Dobie and coworkers use minimum spanning trees to find road networks in satellite and aerial imagery.
\
fan
\!gdraw
 Fan Chung's graph
drawing page.
\
fast hierarchical
\!quadtree
\!astro
\!molmod
 Fast
hierarchical methods for the nbody problem, CS 267, Berkeley, 1995.
\
finding quasar
\!astro
\!mst
 Finding
quasar superstructures.
M. Graham and coauthors use 2d and 3d minimum spanning
trees for finding clusters of quasars and Seyfert galaxies.
\
finite elements
\!meshgen
 Finite Elements Corner.
\
fixturenet
\!grasp
 FixtureNet, an
interactive application for constructing fixtures.
\
fixturing
\!grasp
\!cam
 Fixturing and
setup planning. From a paper on automated manufacturability
analysis at U. Maryland, the contents page of which seems to be missing.
\
float
\!voronoi
\!graphics
 Floating
Points. Deussen, Hiller, van Overveld, and Strothotte use Voronoi
diagrams to place stipple points for
nonphotorealistic rendering.
\
font
\!typography
\!medial
 Font
Wizard Algorithm. Howard Trickey of Bell Labs describes his
software for producing threedimensional renderings of letterforms,
including a straight skeleton like algorithm for achieving a beveled
effect.
\
formal
\!typography
\!medial
 A formal approach to lettershape description for type design.
P. Ghosh and C. Bigelow describe character shapes in terms of their
medial axes.
\
fractal analysis
\!medic
 Fractal analysis of trabecular bone.
M. L Richardson and T. Gillesby discuss algorithms
for automatically estimating fractal dimension,
and their use in modeling bone tissue.
\
fractal dimensions
\#carto
\# 404 22 May 2000
 Fractional Dimensions in Geography with Applications for GIS: An Annotated Bibliography, M. Braun.
\
fractals
\!arch
 Fractals: New Ways
of Looking at Cities. M. Batty reviews an article in Nature
by Makse, Havlin and Stanley.
\
franklin
\!carto
 William
Franklin of Rensselaer Polytechnic
combines computational geometry and cartography in his research.
\
franklin
\!relate
 William Franklin's list of research projects
includes many applications of geometric and related problems
to areas including cartography, air defense, NC machining,
graphics, photointerpretation, and hardware testing.
\
from comp
\!graphics
\!meshgen
\!sci
 From
computational geometry to computational physics, M. Pellegrini,
ERCIM News, Apr. 1996.
Marco describes his recent work on algorithms for form
factors, radiosity, and electrostatics, using integral geometry and
Monte Carlo methods in place
of the traditional finite element meshing approach.
\
galaxy formation
\!astro
\!quadtree
 Galaxy formation with nbody simulations.
J. K. Salmon et al. study galaxy formation by simulating systems of
roughly 10^7 particles, using codes based on a kDtreelike recursive
orthogonal partition.
\!astro
This page also briefly mentions applications of related
octree techniques to molecular dynamics, fluid dynamics, physical chemistry,
data compression, visualization, and data mining.
\!astro
\
gallery
\!gdraw
\!soc
 Gallery
of social structures, L. Krempel, MaxPlanckInst. Köln.
Graph drawing applications in sociology.
\
game
\!vidgames
 Game
programming resources, C. Ericson, Neversoft Entertainment.
\
gatling
\!index
\!metro
 Gatling guns.
Computational questions related to Matousek's work on violated constraints,
from a problem of testing guns.
\
geiger
\!medic
 Bernhard
Geiger of INRIA works on problems of surface reconstruction in
medical imaging.
\
geodetic
\#carto
 Geodetic Software Systems,
geomatics information center.
Links to various academic and commercial GIS web resources.
\
geographic
\#carto
\# no such host 22 May 2000
 Geographical data
visualization, U. Valencia.
\
geometric and solid
\!csg
 Geometric and solid modeling links, Jeongyoon Lee, Korea.
\
geometric approach
\!meshgen
\!cad
 "Geometric approaches to mesh generation",
by Christoph Hoffman of Purdue,
argues for a tighter coupling between mesh generation
and computer aided design.
\
geometric aspects
\!molmod
 Geometric aspects of protein structure, Duke U.
\
geometric morphology
\!soil
\!delaunay
\!medial
 Geometric morphology of granular materials.
B. R. Schlei, L. Prasad, and A. N. Skourikhine
use constrained Delaunay meshing and chordal axis transforms
to identify grains and determine statistical features
in micrographs of porous media in order to obtain input for
hydrodynamic calculations.
For more information,
see Schlei's web site,
and their additional papers
"A
geometric transform for shape feature extraction" and
"Featurebased syntactic and metric shape recognition".
\
geometric morphometrics
\!bio
 Geometric
Morphometrics, the study of changing shape and its application to
evolutionary biology.
\
geometry center
\!geom
 The Geometry
Center, Univ. of Minnesota, is mainly concerned
with visualization of mathematics, but has occasional
information of interest to computational geometers.
\
geometry conf
\!geom
\!index
 Geometry conferences.
\
geometry courses
\!geom
\!index
 Geometry courses and teaching materials.
\
geometry for computer graphics
\!graphics
 Geometry for computer graphics. Teaching materials from the ITTI Gravigs
Project.
\
geometry forum
\!geom
 The Geometry Forum,
Swarthmore College, concerns itself
with K12 geometry education, but also maintains
a geometry research mailing list with
archives on their web site.
\
geometry journals
\!index
\!geom
 Geometry journals.
\
geometry junkyard
\!geom
 The Geometry
Junkyard, David Eppstein, UC Irvine.
A mix of recreational geometry and research problems.
\
geometry lab
\!meshgen
 The Geometry
Laboratory at NASA's Langley Research Ctr.
\
geometry lit
\!geom
 Geometry Literature Database, maintained by Bill Jones, Otfried Schwarzkopf, and Jeff Erickson.
\
geometry pub
\!geom
\!index
 Geometry publications by author.
\
geometry ref
\!vision
 Geometry references for computer vision.
From Fleck and Stevenson's
Computer Vision Handbook.
\
geometry research
\!index
\!geom
 Geometry research groups.
\
geophysical
\!carto
\!interpolate
 Geophysical
applications of natural neighbors.
A group at ANU Canberra uses Voronoi diagram based interpolation
for a range of geophysical problems.
\
ghosh
\!metal
\!voronoi
 Somnath Ghosh
uses Voronoi diagrams as part of a system for quantitative metallography.
\
gis and cad
\!carto
\!cad
\!arch
\!index
 GIS and CAD.
John Thomas describes Rochester's experience with the interface
between GIS (for largescale geographic data) and CAD
(for smaller scale architectural information such
as street layout).
\
gis net sites
\#carto
\# 404 22 May 2000  ~frank is there but empty
 GIS Net Sites, Frank
Smith, NetSource.
\
gnu
\!mesh
\!csg
\!delaunay
 The Gnu Triangulated Surface library. Providing robust primitives for mesh representation, constructive solid geometry operations, and Delaunay triangulation.
\
goldberg
\!cam
 Ken
Goldberg describes a problem of computing (probabilities of)
all stable placements of a polyhedron, which he used
in modeling part feeder systems.
\
graph drawing
\!gdraw
 Graphdrawing.org
clearinghouse for graph drawing research.
\
graph drawing
\!gdraw
 Graph
Drawing, Roberto Tamassia, Brown U.
This page contains pointers to a
long annotated bibliography, a graph drawing tutorial, and
information on the annual Graph Drawing conference.
\
graph drawing conf
\!gdraw
\!conf
 Graph Drawing:
GD '92 and '93 reports, programs, and proceedings
(TeX and PS formats).
GD
'97, Rome, Sept. 1997.
GD
'98, Montreal, Aug. 1998.
GD '99, Prague, Sep. 1999.
GD '00, Virginia, Sep. 2000.
GD '01, Vienna, Sep. 2001.
GD '02, Irvine, Sep. 2002.
GD '03, Perugia, Sep. 2003.
\
graph drawing research
\!gdraw
 Graph
drawing research, A. Frick, Karlsruhe.
\
graph partitioning
\!meshgen
\!align
\!teach
 Graph partitioning.
Geometric methods for finding graph separators.
Lecture notes from CS267, UC Berkeley, on high performance computing.
This problem has applications in scientific computation,
and, apparently, in DNA sequencing.
\
graphlet
\!gdraw
 Graphlet,
a toolkit for implementing graph editors and graph drawing algorithms.
\
graphml
\!gdraw
 GraphML
XMLbased language for standardization of graph drawing software
input/output formats.
Other previously used graph formats include
MALF,
edge list, node edge list, parenthesized,
GXL,
GraphXML,
GML,
LEDA.GRAPH,
XGMML,
BCG,
Aldebaran,
graph6 (g6), and sparse6 (s6),
so there is obviously a lot of benefit to be gained from standardization.
\
graphviz
\!gdraw
 GraphViz package: dot and
neato graph drawing software, E. Koutsofios and S. North.
\
green island
\!carto
\!timber
\!voronoi
 The
Green Island Formation in Forest Fire Modeling with Voronoi
Diagrams, Roque and Choset, CGC98.
\
grid evolution
\!meshgen
\!quadtree
\!vlsi
 Grid Evolution for Oxidation Simulation. Sahul, McKenna, and Dutton (in this paper from the NUPAD V Conf.) use adaptive quadtree meshes to simulate semiconductor oxidation.
\
grid generation
\!meshgen
 Grid generation
thrust, Mississippi State U.
\
grip
\!molmod
 GRIP:
computer graphics for molecular studies, UNC.
\
ground states
\!sci
 Ground
states of a ternary fcc lattice model.
D. Avis and K. Fukuda apply their work on listing vertices of polytopes
to a problem of finding possible ground states in alloy structures.
\
grouping
\!char
\!voronoi
 Grouping words and multipart symbols.
M. Burge and G. Monagan use Voronoi diagrams for document analysis.
\
guaranteeing
\!metro
 Guaranteeing
bounds on uncertainty in metrology. A. Neumaier advocates interval
arithmetic as an approach to robustness in geometric computation.
\
gvf
\!gdraw
 GVF, opensource
Java graph visualization framework.
\
hausdorff
\!vision
 Hausdorff Distance Image Comparison,
Dan Huttenlocher, Cornell.
\
heckbert
\!meshgen
 Paul Heckbert's
collection of mesh generation links.
\
hexahedral
\!index
\!meshgen
 Hexahedral subdivision.
William Thurston characterizes the polyhedra which
can be subdivided into topological cubes meeting facetoface.
\!index
The same characterization was independently rediscovered
by Scott Mitchell of Sandia Labs. For related work,
see
"A
Characterization of the Quadrilateral Meshes of a Surface which
admit a Compatible Hexahedral Mesh of the Enclosed Volume",
Scott Mitchell, 5th MSI Worksh. Comp. Geom.,
and my paper,
"Linear Complexity Hexahedral Mesh Generation".
\!index
\
hexar
\!meshgen
\!csg
 HEXAR
(Cray Research) is an automatic unstructured hexahedral mesh generation package
that starts working directly from
computeraided design (CAD) surface data.
\
hobby
\!typography
 John Hobby's paper "Polygonal approximations that minimize the number of
inflections" (from SODA 1993) describes a form of outline
simplification with applications including optical character
recognition, and includes references to similar work.
Hobby has also worked on other typographic algorithms including
automatic
generation of lowresolution hinting information from font outlines.
\
human organs
\!medic

Human organs in polygonal slice format,
Gil Barequet, Tel Aviv U.
\
ieee rob
\#assembly
 IEEE
Robotics & Automation Soc.,
Assembly & Task Planning Technical Committee
\
igis
\!carto
 IGIS '94 (Int. Worksh. Advanced Research in Geographic Information
Systems) table of contents.
\
ima
\!meshgen
\!conf
 IMA Workshop: Grid Generation and Adaptive Algorithms, April 1997.
\
image proc
\!vision
\!hull
\!soil
 Image
Processing and Pattern Recognition in Soil Structure. D. Luo of
Glasgow uses convex hulls and other geometric techniques to analyze
images of soil particles.
\
image pyramids
\!quadtree
\!sigproc
 Image
pyramids and trees, quadtree data structures for
binary tree predictive image coding.
\
image reg
\!mst
\!vision
 Image tilings.
The PRISME group at INRIA proposes stitching together multiple images of
a scene (e.g. multiple aerial or satellite views of a piece of land)
using a form of Voronoi diagram to choose which image has the best quality
for each piece of scenery.
\
incremental
\!vreal
 Incremental
update of the visibility map as seen by a moving viewpoint in two
dimensions, S. Ghali and A. J. Stewart, Toronto.
\
index
department of redundancy department
\!index
 This index.
\
information geom
\!csg
 Information Geometers Ltd., publishers of books on geometry, CAD/CAM, and graphics including the CSG proceedings.
\
information on finite element
\!meshgen
 Information on finite element mesh generation,
Robert Schneiders, Aachen; very comprehensive.
\
information geometers
\!geom
 Information Geometers,
publisher of specialist technical books and software for geometric computing.
\
integrating geom
\!csg
 Integrating
Geometric and Solid Modeling,
Dinesh Manocha, UNC Chapel Hill.
\
interactive
\!vreal
\!conf
 Interactive Walkthrough of Large Geometric Databases,
full day course, SIGGRAPH, August 1996, New Orleans.
\
international net
\!soc
 International
Network for Social Network Analysis.
\
international soc
\!meshgen
 International
Society of Grid Generation.
\
internet gis
\!carto
 Internet
GIS and remote sensing sites, Queen's Univ., Canada.
\
internet packet
\!telecom
 Internet Packet Filter Management and Rectangle Geometry.
D. Eppstein and S. Muthukrishnan
use orthogonal range searching techniques for finding rules that match
incoming packets, and detecting rule conflicts.
\
interpolation
\#carto
\#interpolate
\# no longer any useful info, just says to contact MO, 22 May 2000
 Interpolation techniques in GIS analysis,
M. Ollila.
\
intractability
\#assembly
 Intractability of assembly sequencing, and/or scheduling, and removing a unit disk, M. Goldwasser and R. Motwani, 1st CGC Worksh. Computational Geom.
The authors show that even simple abstractions of assembly planning
problems are computationally difficult.
\
inverse
\!astro
 Inverse
nearest neighbors for astrophysical Nbody simulations, R. Anderson,
M. Cary, and B. Tjaden, U. Washington.
\
ionic
\!sci
\!voronoi
 Ionic association in electrolyte solutions: A Voronoi
Polyhedra analysis, and
The Voronoi Polyhedra as tools for structure determination in
simple disordered systems.
J.C. Gil Montoro and J.L.F. Abascal investigate the use of Voronoi
diagrams in analyzing chemical simulations.
\
issues
\#csg
\#meshgen
\# no longer exists, 28 Aug 1998
 Issues in geometric and solid modeling,
Brian Grossman, Colorado State U.
Discusses research on shape representation issues
and their connection with hexahedral mesh generation.
\
ivy
\#assembly
 Ivy environment for assembly planning, Iowa State Visualization Lab.
\
japan
\# listed much earlier in conf, here only for recent
 Japan Conf. Discrete & Computational Geometry '98
\
jgraph
\!gdraw
 JGraph
componentbased Java software for drawing graphs for business users and
domain specific data.
\
jgraphed
\!gdraw
 JGraphEd,
Java graphediting software with many builtin graph algorithms.
\
jiang
\!vreal
 H.
Jiang's research in collision detection.
\
kinematics
\!cad
\!cam

Kinematicsdriven Geometric Modeling: A Framework for Simultaneous
Sculptured Surface Design and CNC Tool Path Generation,
Q. Jeffrey Ge, 5th MSI Worksh. Comp. Geom.,
makes a case for tighter coupling between CAD and CAM.
\
label
\!carto
 Labeling a rectilinear map,
Andy Mirzaian and Binhai Zhu, 5th MSI Worksh. Comp. Geom.
\
lcts
\!meshgen
\!recent
\# 10 Mar 2004
 LCTS project,
package for quality mesh generation and finite elements,
Roman Galkin.
\
learning
\!vision
\!mst
 Learning
salient features for realtime face verification, K. Jonsson, J. Matas,
and J. Kittler. Includes a minimumspanningtree based algorithm
for registering the images in a database of faces.
\
level
\!vlsi
\!medic
\!robot
\!sigproc
 Level set
methods for following the evolution of interfaces, J. Sethian,
Berkeley. The basic idea is to solve various "advancing front" type problems
such as finding shortest paths around obstacles, by evolving a surface
in one higher dimension that describes the dynamics of the front.
Includes movies and Java applets describing applications to
VLSI design, medical image processing, noise removal from images, and
robot motion planning.
\
levels
\!vreal
 Levels of
detail bibliography and links, M. Krus, CNRS.
\
localization
\!robot
 Localization and navigation using laser radar. This project at U. Würzburg uses visibility polygon matching to determine robot locations.
\
lodestar
\!vreal
 Lodestar
levelofdetail generator for VRML.
\
map label
\!carto

MapLabeling Pages,
Alexander Wolff
\
mathematical frame
\!csg
 A
Mathematical Framework for Sculptured Solids in Exact CSG
Representation, Jai Menon and Baining Guo, 5th MSI Worksh. Comp. Geom.
\
medial axis for chamfer
\!medial
 Medial
axis for chamfer distances in 2d, 3d and 4d.
E. Remy and E. Thiel describe algorithms for computing medial axes
for certain polyhedral distance functions.
\
medial axis pruning
\!medial
\!vision
 Medial
axis pruning. Robert Ogniewicz of Harvard uses medial axes for
shape recognition.
\
medial axis transform
\!char
\!medial
 Medial axis
transformation and its application to seal imprint verification.
Y.M. Fuh uses medial axis skeletonization as part of a method for detecting
forgeries in Chinese signature blocks.
\
medical image vol
\!medic
 Medical Image Volume Visualization Software FAQ.
\
medical imaging
\!medic
 Medical imaging links, M. Joppe, Bremen.
\
mesh generation bib
\!meshgen
 Mesh generation
bibliography with emphasis on anisotropic unstructured triangular
meshes, P. Heckbert and F. Bossen.
\
mesh generation mail
\!meshgen
 Mesh
generation mailing list, Steve Owen, CMU.
\
mesh generation for bio
\!meshgen
\!bio
 Mesh generation
for bioelectric field problems,
Oak Ridge Nat. Lab.
Discusses general mesh generation techniques as well as some
of the problems arising in this application
(such as anisotropy of some tissue types).
\
mesh generation related info
\#meshgen
\# no longer exists, 28 Aug 1998
 Mesh
GenerationRelated Information, Greg Sjaardema, Sandia Labs.
\
mesh generation research
\!meshgen
 Mesh
Generation research by Paul Chew at Cornell
\
mesh generation software
\!meshgen
 Mesh
generation software
from
Nina Amenta's CG software directory.
\
mesh generation using relaxation
\!meshgen
 Mesh
generation using relaxation in warped space, P. Heckbert and
F. Bossen.
\
mesh generators
\!meshgen
 Mesh
Generators, from
Ian MacPhedran's hypertext version of Roger Young's finite element resources catalog.
\
mesh redux
\!meshgen
 Mesh Reduction, Shastra project, U. Texas.
\
meshing research corner
\!meshgen
 Meshing Research Corner, Steve Owen, CMU.
\
\!delaunay
 Delaunaybased methods in mesh generation, from Steve Owen's
Meshing
Research Corner.
\
\!medial
 Medialaxisbased methods in mesh generation, from Steve Owen's
Meshing
Research Corner.
\
\!quadtree
 Octreebased methods in mesh generation, from Steve Owen's
Meshing
Research Corner.
\
meshing roundtable
\!meshgen
\!conf
 Annual Meshing Roundtables:
4th Roundtable, Sandia, 1995:
conf.
info. and
papers.
5th Roundtable, Pittsburgh, October 1996.
6th Roundtable, Park City, Utah, October 1997.
7th Roundtable, Detroit, October 1998.
8th Roundtable, Lake Tahoe, October 1999.
9th Roundtable, New Orleans, October 2000.
\
minimal spanning
\!bio
\!mst
 Minimal
spanning tree analysis of fungal spore spatial patterns,
C. L. Jones, G. T. Lonergan, and D. E. Mainwaring.
\
minimal spanning
\!astro
\!mst
 A minimal spanning tree analysis of the CfA redshift survey. Dan Lauer uses minimum spanning trees to understand the largescale structure of the universe.
\
minkowski
\!astro
\!cad
 Minkowski
Operations for Satellite Antenna Layout, JD. Boissonnat, E. de
Lange, and M. Teillaud, SCG 1997.
\
mixing
\!sci
\!mst
 A
mixing model for turbulent reactive flows based on Euclidean minimum
spanning trees, S. Subramaniam and S. B. Pope.
\
model simplif
\!vreal
 Model
simplification. Work at UNC on automatic
methods to produce visually accurate multiresolution polygonal
simplifications of 3D datasets. See also the UNC
Simplification
Envelopes project and source code.
\
modeling
\!arch
 Modeling
and rendering architecture from photographs, P. Debevec, C. Taylor,
and J. Malik, Berkeley.
\
modeling
\!metal
\!voronoi
 Modeling
of microstructures by Voronoi cells. M. Nygärds and P. Gudmundson
use the grain structure of a randomly generated Voronoi diagram with
periodic boundary conditions to model ferrite/pearlite steel.
\
moebius
\!arch
 Moebius
architecture, C. Séquin, UC Berkeley. (Includes also a discussion
of software tools for analyzing building shapes.)
\
molecular
\!molmod
 Molecular Geometry References, D. AbrahamsGessel, Dartmouth.
\
mosaic
\!voronoi
\!graphics
\!interpolate
 Mosaic / stained glass graphic effect. One gets interesting
visual effects by taking a random sample of pixels from a bitmap image,
computing the Voronoi diagram of the sample, and filling each cell
with the corresponding sample's color. This appears to be what
Photoshop does in its "Pixelate>Crystalize" filter;
it can be thought of as a form of piecewise constant function interpolation.
\
mosaicexpress
\!graphics
\!arch
\!recent
\# 27 May 2004
 MosaicExpress and Mosaïque 2000 PC software for designing and building tile mosaics, based
on square, hexagonal, triangular, and other tilings of the plane.
\
motion
\!robot
 Motion planning literature search,
J. Vleugels and P. Svestka, Utrecht.
\
my own
\!gdraw
 My own research on
graph drawing.
\
\!meshgen
 My own research on mesh
generation and optimal triangulation.
\
\!quadtree
 My own research on
quadtrees and related hierarchical decompositions.
\
nanotech
\!molmod
 Nanotechnology, Ralph Merkle, Xerox PARC.
\
nanotech and molecular
\!molmod
 Nanotechnology and molecular modeling on the WWW,
Sean Morgan.
\
navigating
\#carto
\#voronoi
\# 404, asked Gold for new addr, 7 Mar 2000
 Navigating
in the map. Anton Castro Francois and Chris Gold use Voronoi diagrams
to embed users' points of view in maps and enable the users to interact
with sets of local features.
\
near neighbor
\!datamine
 Near Neighbor
Search in Large Metric Spaces, S. Brin, Stanford U.
\
network sci
\!molmod
 Network Science: computational chemistry.
\
nexus
\!vidgames
 The
Nexus game programming page.
\
nih molecular
\!molmod
 The NIH Molecular
Modeling home page. (Warning: lots of incredibly annoying cookies.)
\
nimeroff
\!arch
\!graphics
 Jeffry
Nimeroff works with both the Computer and Information
Science and Architecture depts. at U. Penn., on illumination
algorithms for architectural computer graphics.
\
nist proj
\!metro
 NIST projects in computational geometry and metrology
\
nist yearly
\!metro
 NIST Yearly Reports, 1995: Computational Geometry and Metrology
\
novel
\!arch
\!medial
 A
novel type of skeleton for polygons. Aichholzer, Alberts,
Aurenhammer, and Gärtner define the "straight skeleton", a
geometric construction resembling the medial axis and
potentially useful in defining rooflines of buildings.
(Warning: lots of incredibly annoying cookies.)
\
object representation
\!csg
\!quadtree
 Object Representation by Means of Nonminimal Division Quadtrees and Octrees.
This paper by Ayala et al., in ACM Trans. on Graphics,
describes quadtree methods in solid modeling.
\
open
\!metro
 Open
Problems in Computational Metrology,
C. Duncan, Johns Hopkins.
\
optimizing
\!cam
 Optimizing part quality with orientation,
D. Thompson and R. Crawford, U. Texas. Defines measures that relate
quality to the orientation of a part and describes algorithms for
finding optimal orientations.
\
other sites
\!datamine
 Other Sites
Relevent To Data Mining, Andy Pryke, Birmingham.
\
panose
\!typography
 The Panose
typefacematching system condenses various geometric characteristics
of characters into a short numerical vector in order to measure the
similarity between different fonts.
\
paradigm
\!carto
 The Paradigm Group
at Carleton U., research into parallel algorithms for geographic
information systems.
\
parallel nbody
\!quadtree
\!astro
\!molmod
 Parallel
nbody simulations using hierarchical octree representations of space.
\
parallel octree
\!meshgen
\!quadtree
 Parallel octree mesh generation project,
Ralf Diekmann, Paderborn.
\
parberry
\!vidgames
 Ian Parberry's
Laboratory for Recreational Computing.
\
part layout
\!textile
 Part Layout and Optimization of Part Shape,
L. Shanley, L. Anderson, and V. Milenkovic, research brief from the
National Textile Center.
\
partition
\!astro
\!quadtree
\!voronoi
 Partition
based point pattern analysis methods for investigation of spatial
structure of various stellar populations, L. Pásztor, ADASS '94.
\
percolation
\!sci
\!voronoi
 Percolation. Ted Davis of U. Minn. uses Voronoi diagrams
to simulate fluid flow through porous media.
\
petroleum
\!carto
\!voronoi
 Petroleum reservoir simulation. Santosh Verma of Stanford uses
Voronoi diagrams "to accurately represent horizontal and deviated
wells, local flow geometry, faults, major heterogeneities, etc" in
petroleum reservoir simulation.
\
physical
\#interpolate
\#graphics
 Physical cloth simulation. A. Shelat and R. Surdulescu of Harvard model a hanging cloth by interpolating a surface to points placed on catenary curves. The intent seems to be to generate some sort of graphical verisimilitude rather than actually simulate gravity, tension, etc within the cloth.
\
pneumonea
\!medic
\!hull
 Pneumonea
and tuberculosis diagnosis. Jason Everhart of Los
Alamos uses convex hulls as part of a heuristic for estimating the
percentage of lung volume occupied by a pneumonea infection.
This initial guess of the lung contour is then iteratively refined
to a more accurate representation.
\
pocket machining
\!cam
 Pocket machining. Martin Held has two papers available on planning
problems for this method of manufacture:
"Pocket
Machining Based on ContourParallel Tool Paths Generated
by Means of Proximity Maps" and
"Optimization
Problems Related to Zigzag Pocket Machining".
\
probabilistic alg
\!grasp
 Probabilistic Algorithms for Efficient Grasping and Fixturing.
This paper by Marek Teichmann, at the 5th MSI Worksh. Comp. Geom.,
shows that grasping and fixturing are
related by geometric duality to problems of approximating manyfaceted
convex polyhedra by
simpler shapes (previously studied for their application in
graphics).
\
processing
\!medic
\!quadtree

Processing and display of medical three dimensional arrays of numerical
data using octree encoding, Amans and Darrier, Proc. SPIE, 1985.
\
programmers
\!graphics
 Programmer's
Heaven computer graphics programming links.
\
protein
\!voronoi
\!molmod
\!recent
\# 14 Jun 2004
 Protein
secondary structure assignment through Voronoi tesselation,
Dupuis, Sadoc, and Mornon.
\
prove
\!voronoi
\!molmod
 Prove protein volume evaluation software. This project at the
Free University of Brussels
uses Voronoi diagrams and weighted Voronoi diagrams to
analyze the portion of a molecule's volume taken up
by each atom in the molecule.
Mark Gerstein at Stanford has a directory with
very similar software and related papers.
\
puertra
\!graphics
 PUERTRA, software for modeling Islamic geometric art.
\
qhull
\!voronoi
\!delaunay
\!recent
\# 26 Mar 2004
 Qhull software for
convex hulls, Delaunay triangulations, Voronoi diagrams, and halfspace
intersection about a point.
\
qmg
\!meshgen
\!quadtree
 QMG, a quadtreebased 2d and 3d mesh generator by Steve Vavasis of Cornell.
\
quadtree const
\!quadtree
 Quadtree
constants. Steven Finch investigates the expected behavior of random
quadtrees.
\
quadtree ref
\!quadtree
 Quadtree references from Michael Ley's bibliography of database systems and logic programming.
\
quadtree structured
\!sigproc
\!quadtree
 A Quadtree Structured Videophone Codec, L. Hanzo and A. Schober,
Southampton.
\
quasiconformal
\!carto
 Quasiconformal maps of the Earth, M. Hurdal.
\
raindrop geomagic
\!csg
 Raindrop Geomagic Inc.
geometric modeling and visualization software.
\
rayasan
\!molmod
 Rayasan
molecular modeling toolkit, Shastra project, U. Texas.
\
realtime octree
\!quadtree
\!vision
 Realtime
octree generation from rotating objects
(abstract
or full
paper).
R. Szeliski of DEC uses octrees in computer vision.
\
reconstruction
\!carto
\!voronoi
 Reconstruction of geological data using 3d Voronoi diagrams. From the PRISME project at INRIA.
\
reconstruction
\#interpolate
 Reconstruction of surfaces and scalar fields from 3D scans, Shastra project, U. Texas.
\
representation and eval
\!csg
 Representation and Evaluation of Boolean Combinations of NURBS Solids,
Shankar Krishnan, Dinesh Manocha, and Atul Narkhede, 5th MSI
Worksh. Comp. Geom.
\
resources for carto
\!carto
 Resources for
cartography, GIS, and remote sensing,
U. Wisc. Stevens Point, Dept. of Geography/Geology.
\
restrict/eval
\!textile
 The Restrict/Evaluate/Subdivide Paradigm for Translational
Containment,
Karen Daniels, 5th MSI Worksh. Comp. Geom.
\
review
\!metro
 A Review
of Current Geometric Tolerancing Theories and Inspection
Data Analysis Algorithms, S. Feng and T. Hopp, US Dept. Commerce, 1991.
\
riemann
\!voronoi
 Riemann surfaces and algebraic curves. Juha Haataja
(Ctr. for Scientific Computing, Finland)
describes some applications of Voronoi diagrams
(aka Dirichlet polygons) in pure mathematics.
\
robotics resource
\!robot
 Robotics Resource Page, Data Recovery Labs.
\
robotics papers
\!robot
\!grasp
 Robotics
papers and preprints, list of online papers on sensor based
planning, grasping and fixturing, locomotion, and other robotics topics,
maintained by Howie Choset, CMU.
\
rocpack
\!soil
\!sci
 Rocpack  A 3D Particle Packing Algorithm".
Sphere packing applications in rocket propellant particle simulations.
Part of a larger package for simulating solidgas combustion interfaces.
Similar ideas look likely to be useful for simulating soils or other
particulate materials.
\
roofer
\!arch
 Roofer subroutine
package for designing roofs from ground wall layout. Similar roof
design capability is also built into the
3D Home Architect
and Chief Architect
programs.
\
rotating calipers
\!geom
 Rotating Calipers.
\
sanner
\!molmod
 Michel Sanner of Scripps studies algorithms for molecular modeling,
and published a paper on molecular surface accessability
at the 11th ACM Symp. Comp. Geom.
\
satellite
\!cad
 Satellite
antenna layout. How to place components on a satellite so they
don't interfere with each other, using geometric techniques including
decomposition of polyhedra into convex pieces.
\
sausage
\!molmod
\!mst
 Sausages,
proteins, and rho. In the talk announced here, J. MacGregor Smith
discusses Euclidean Steiner tree theory and describes potential
applications of Steiner trees to protein conformation and molecular
modeling.
\
scale
\!medial
 Scale space
skeletonization. Pixelbased medial axis transform techniques by
L. da F. Costa and L. F. Estrozi.
\
scanning
\#interpolate
 Scanning
and surface interpolation links, Dimitri PapadopoulosOrfanos, ENST.
\
schevon
\!cam
 An geometry problem arising in a special case
of manufacturing
concerns forming parts out of folded
sheet metal  one must unfold the part
to a flat surface that does not overlap itself. This can always
be done for convex polyhedra if one can cut faces, but it is open
whether one need only use cuts along edges.
Touch3d is commercial software for making unfolded models for rapid prototyping; according to MacUser
(Jul '97 p.52), "components often overlap" requiring extensive user
interaction, so they need better unfolding algorithms!
I've collected several more unfolding
references in my junkyard.
\
schnyder
\!gdraw
 Schnyder's gridembedding algorithm.
Lecture notes for two graph algorithm classes.
\
schwarz
\!sigproc
 Dr. Christian Schwarz's home page at the MaxPlanckInst. fuer
Informatik includes pointers to longer versions of his papers on
finding minimal enclosing parallelograms and on the application of
this problem to rational decimation systems.
\
seth
\!arch
\!graphics
 Seth Teller
of MIT is constructing a database
of buildings in Cambridge Mass. Related algorithmic questions
include methods for combining image data from different
sources into a single 3d model, and data structures for fast rendering
of the resulting graphics.
\
settlement
\!carto
\!voronoi
 Settlement
selection for interactive display. How to choose which towns to show
on a map, when the scale is too low to show everything?
M. van Kreveld, R. van Oostrum, and J. Snoeyink describe algorithms
based on incremental maintenance of Voronoi diagrams.
\
shape based 4d
\!medic

ShapeBased 4D Left Ventricular Myocardial Function Analysis.
P. Shi, A. Amini, G. Robinson, A. Sinusas, C.T. Constable, and J. Duncan,
Yale U. Reconstructs heart membranes by triangulation of contours.
Their version of the problem is complicated by the extra dimension
of timevarying data.
\
shape modeling int
\!csg
\!conf
 Shape
Modeling International '97, Japan, March 1997.
\
shape modeling with
\!csg
 Shape modeling with real functions.
U. Aizu, Japan.
\
shape recon
\!medic
 Shape
reconstruction software
from
Nina Amenta's CG software directory.
\
sibgrapi
\!graphics
\!conf
 SIGRAPI 2001,
14th Brazilian Symposium on Computer Graphics and Image Processing,
Santa Catarina, 1518 October 2001.
Lists computational geometry as one of the possible submission topics.
\
simplicialview
\!control
\!delaunay
 SimplicialVIEW, a package for robust stability
analysis, uses Delaunay triangulations as part of an iterative
refinement sheme to approximate the crossover of a robust control problem.
\
sity
\!arch
\!voronoi
\!medial
 Sity.
Tom Kelly appears to be creating artificial cityscapes by using Voronoi diagrams of sites with lots of collinearity to form the city blocks and streets, similar Voronoi diagrams within the blocks to form property boundaries and building floorplans, and straight skeletons for the rooflines.
\
skeleton
\!medic
\!voronoi
\!delaunay
\!medial
 Skeleton and
boundary extraction. Glynn Robinson of Yale overlays the Delaunay
triangulation and Voronoi diagram of points sampled from a surface
(the boundary between different features in a medical image) and
somehow extracts from them subsets representing the surface itself and
its medial axis.
\
smart
\!molmod
 SMART: A
solventaccessible triangulated surface generator for molecular graphics
and boundary element applications, R. J. Zauhar,
J. ComputerAided Molecular Design 9 (1995) 149159.
\
soap
no longer there (N&S are at traffic project under comphys but no foam) 11/99
\#sci
\#voronoi
 Soap froth. Lutz Neubert and Michael Schreckenberg of Duisberg
use Voronoi diagrams as an initial condition for investigating
the evolution of soap bubble froths.
\
solid freeform
\!cam
 Solid
freeform fabrication.
A group at U. Texas describes geometric problems arising in planning
for laser sintering and laser deposition processes.
\
source
\!index
 Source file, run through
filter to produce
most of the files in this directory.
 Shell script to control execution of
filter.
\
space frame
\!arch
 Space Frame.
Forms and structures generated by identical triangles.
\
sparse
\!align
 Sparse dynamic programming, D. Eppstein et al., SODA 1990 and JACM 1992.
\
spatial
\!carto
\!delaunay
\!telecom
 Spatial
modelling by Delaunay networks. Terje Midtbø explains applications
of Voronoi diagrams to "subjects such as determination of areas covered
by a mobile telephone transmitter, determination of highwater marks in
rivers, determination of noise zones along roads, drawing voltage maps,
and other, more conventional cartographic tasks."
\
speedups
\!csg
 Speedups in constructive solid geometry, D. Eppstein, UCI, 1992.
\
spherulites
\!voronoi
\!soil
\!bio
 Spherulites,
a crystal growth formation closely related to Voronoi diagrams and
arising in modeling of geological materials, vitamins and red blood
cells, and thermoplastics.
\
spie
\!vision
\!conf
 SPIE Signal and Image Processing publication list
contains abstracts from several vision conferences with geometric
content, notably Vision Geometry
(I,
II,
III,
IV) and
Geometric Methods in Computer Vision
(I,
II)
\
stanford assembly
\#assembly
 Stanford Assembly Analysis Tool, Robotics Lab., Stanford U.
\
statistical geom
\!molmod
\!delaunay
 Statistical
Geometry of Protein Structure. I. Vaisman performs statistical analysis
on Delaunay triangulations of protein atoms to find preferred clusters
of amino acids.
\
straight skeleton
\!medial
\!bio
 Straight skeleton implementation.
Petr Felkel and Stepán Obdrzálek apply this medial axis variant
to segmentation of images of placentas as a preliminary step in shape
reconstruction from contours.
\
strat
\!relate
 Strategic directions in computing research, computational geometry working group.
\
stripe
\!graphics
 Stripe
tool for converting polygonal models into triangle strips, for fast
output to graphics hardware.
\
structure det
\!sci
\!voronoi
 Structure determination in disordered systems.
J.C.G. Montoro and J.L.F. Abascal use Voronoi polyhedra to detect
clusters in rapidly quenched liquids.
\
symp comp
\!cad
\!conf
 Symp. Comp. Geom. for Mechanics & Appl., Vienna, Austria, July 2002.
\
symp trends
\!meshgen
\!conf
 Symposia on Trends in Unstructured Mesh Generation:
1st Symp.,
Joint ASME/ASCE/SES Summer Meeting, Northwestern U., June 1997
2nd Symp.,
5th US Nat. Cong. Comp. Mech., Boulder, August 1999
\
system for extract
\!arch
 A system for extracting morphological information from architectural drawings, C. Terzidis and E. Vakal, U. Michigan.
Similar work was also recently presented by B. Kernighan and C. Van Wyk at
the 1st ACM Worksh. Applied Computational Geometry.
\
terrain model
\#carto
\#interpolate
 Terrain
modeling. Paul Bourke describes an incremental Delaunay
triangulation algorithm, discusses how DT interpolation
fits with the characteristics of terrain modeling problems,
and provides a short bibliography.
\
tesarna
\!medial
\!char
\!cam
 Tesarna Typesetter Program
uses medial axes to produce carved lettering by a computer controlled router.
\
three d engines
\!vidgames
\!vreal
 3d Engines
for realtime graphics.
\
three d medial
\!soil
\!medial
 Three
Dimensional Medial Axis Analysis of the Void Structure of Geological
Materials, Coker, Lindquist, and Lee, BAPSPC '95. (Abstract only.)
See also Medial axis
analysis of three dimensional tomographic images of drill core
samples, a journal submission by the same authors.
\
three d morphing
\!graphics
 3d
Geometric Morphing, R. Rohrer, George Washington U.
\
three d views
\!timber
 3D views of
some optimal log cutting patterns, S. F. Bellenot, Florida State U.
\
three d tutte
\!gdraw
 Threedimensional
Tutte embedding, K. Chilakamarri, N. Dean, and M. Littman.
Threedimensional convex drawing of nonplanar graphs.
\
time critical
\!vreal
\!medial
 Timecritical
collision detection. Philip Hubbard uses medial axes to find
multiresolution approximations of a shape by unions of spheres,
and uses these approximations for fast collision detection.
\
tollis
\!gdraw
 Ioannis Tollis'
graph drawing research and
papers.
\
tom sawyer
\!gdraw
 Tom Sawyer Software,
producers of commercial graph drawing and editing software.
\
topological data structures
\!carto
\!recent
\# 9 Apr 2004
 Topological Data Structures for Surfaces: An Introduction for Geographical Information Science.
Book of GIS papers edited by S. Rana.
\
topological disorder
\!vlsi
\!sci
\!delaunay
 Topological
Disorder and Conductance Fluctuations in Thin Films. K. Abkemeier
and D. Grier use Delaunay triangulations of randomly perturbed lattice points
to form resistor networks that model the electrical behavior of
amorphous and polycrystalline silicon.
\
transforming
\!carto
 Transforming
contour maps into digital elevation models, Michael Gousie, Wheaton
College.
\
triangle
\!meshgen
\!delaunay
 Triangle,
an incremental Delaunaybased 2d mesh generator
by Jonathan Shewchuk of CMU,
part of the
CMU Archimedes project for unstructured finite element computation.
\
triangulating the surface
\#meshgen
\#molmod
\# document contains no data, 28 Aug 1998
 Triangulating
the surface of a molecule, N. Akkiraju and H. Edelsbrunner,
Disc. Appl. Math. 71 (1996) 522.
\
triangulation and mesh
\!meshgen
 Triangulation and
mesh generation open problems, web pages, and usenet postings, from the
Geometry Junkyard.
\
triangulation from mult
\#interpolate
 Triangulation from multiple planar contours.
A. B. Ekoule, F. C. Peyrin, and C. L. Odet,
ACM Trans. Graphics 10 (1991) 182199.
Reviewed by P. Maillot.
\
trim watershed
\!carto
\!medial
 TRIM
Watershed Atlas. This project uses medial axes
to approximate the drainage patterns of watersheds.
Warning: 472kb PDF file. See especially appendix D on page 45
of the PDF, describing the algorithms used by this project.
\
tspbib
\!geom
 TSPBIB,
a comprehensive listing of papers, source code, preprints, technical
reports etc. on the Traveling Salesman Problem.
\
tuceryan
\!vision
\!voronoi
 Mihran
Tuceryan's computational geometry research page describes an
application of
Voronoi diagrams to finding neighbor relationships between image
tokens, and includes bibliographic references to related papers by
Tuceryan, Ahuja, and
others.
\
twelve open
\!robot
\!grasp
 Twelve
open problems in industrial robotics.
\
two dimensional cutting
\!textile
 Two dimensional cutting and packing problems in the textile and leather
manufacturing industry, T. Lengauer, Inst. for Algorithms and
Scientific Computing, German Natl. Research Ctr. for Information
Technology.
\
u washington constraint
\!constraint
 U. Washington ConstraintBased Languages and Systems
\
ucla data mining
\!datamine
 UCLA Data Mining Laboratory.
\
unstructured
\#meshgen
\# no longer exists, 28 Aug 1998
 Unstructured decimation of tessellated domains, Iowa State Visualization Lab.
\
us blm
\!carto
 U.S. BLM archive of
GIS utility software and data.
\
us patent
\!graphics
\!quadtree
\!patent
 US
Patent 3602702 covers the quadtree subdivision of a viewing plane to perform hidden surface removal in computer graphics.
Patent 4694404 covers the use of octrees to implement a nearerobjectfirst
painting order.
Patent 5123084 describes a similar nearestfirst octree graphics method.
Patent
5222201 also concerns octree graphics methods, and describes
a heuristic for speeding up the conversion of objects into octree
representations.
\
\!graphics
\!vreal
\!vidgames
\!patent
 US
Patent 3889107 covers the use of binary space partitions for hidden
surface removal, shadow calculation, and collision detection.
\
\!vision
\!hull
\!patent
 US
Patent 4704694 uses convex hulls to recognize objects from video images.
\
\!robot
\!patent
 US
Patent 4862373 is an early patent on robot motion planning
algorithms, referenced by many later patents on the same subject.
\
\!meshgen
\!patent
 US
Patent 4941114 covers an earcutting method of constructing
unstructured triangular meshes. Another meshing patent,
5214752,
describes an incremental point placement algorithm very similar to the
provablygood meshing method of one of its inventors (Jim Ruppert).
Patent
5440674 appears to be based on a very similar incremental method of Chew.
Meshing patents
4797842 and
4933889
are based on medial axes.
Patent
5315537 covers a wavefrontbased quadrilateral meshing system.
Patent
5345490 covers quadtree and octreebased meshing.
Patent
553206 describes methods of merging tetrahedra to simplify meshes.
\
\!vision
\!patent
 US
Patent 5054098 describes a method of detecting whether a scanned
image has been turned at an angle from the original, using an algorithm
for finding minimum enclosing rectangles along with other techniques.
\
\!hull
\!patent
 US
Patent 5086482 seems to cover giftwrapping methods of computing convex hulls in bitmap images.
\
\!typography
\!patent
 US
Patent 5115479 covers the compression of bitmap data by using spline
curves to represent the image outlines. Isn't that what standard font
formats already did?
\
\!graphics
\!patent
 US
Patent 5129051 covers a slab method of performing trapezoidal
decomposition and its application to scanline conversion in computer graphics
(Patent
4791582).
Patent 5276783 is also on slabbased trapezoidalization.
Patent
5020002 is harder to
decode; it seems to be describing an earcutting trapezoidalization method.
\
\!quadtree
\!sigproc
\!patent
 US Patents
5134480,
5228098,
5444489,
5446806,
5452104,
and
5469212
describe video and image coding methods based on quadtrees.
\
\!char
\!hull
\!patent
 US
Patent 5159645 performs character recognition by using convex hulls
to find the counters in each character. A similar idea also occurs in
Patent
4817166.
\
\!arch
\!patent
 US
Patent 5211692 covers a decorative tiling pattern based on the
geometry of zonohedra. Patents
5155951 and
5448868 cover similar threedimensional building systems.
\
\!graphics
\!patent
 US Patent 5268998 seems to cover graphical display of objects in nonEuclidean or higher dimensional geometries.
\
\!graphics
\!hull
\!patent
 US Patents
5317681 and
5428717 cover methods for finding convex hulls of
polyhedra based on flipping reflex edges, along with an animated version
of this procedure that creates a smooth morph of the polyhedron to its hull.
\
\!window
\!quadtree
\!patent
 US
Patent 5459831 covers the use of quadtrees to perform the range
queries needed for object selection in graphical user interfaces.
\
\!window
\!quadtree
\!patent
 US
Patent 5461712 uses quadtrees to allocate memory to different
objects in a windowing system.
\
\!medic
\!patent
\!hull
 US
Patent 5463721 describes the use of convex hulls in a method for finding a
path for a radiationbeam scanner so it can get enough data
to reconstruct object shapes. Patents
4888693,
4969110,
and
5053958
also use convex hulls for computerized tomography.
\
\!metro
\!grasp
\!hull
\!patent
 US
Patent 5465221 describes a part inspection system including the use
of convex hulls to determine stable orientations.
\
\!char
\!vision
\!hull
\!patent
 US
Patent 5483606 describes a method of registering (lining up) copied
pages with each other in a copying machine, using the convex hulls of
images of the pages.
\
\!textile
\!medial
\!patent
 US
Patents
5506784,
5510994,
and
5541847
use medial axes to generate embroidery patterns.
\
\!window
\!voronoi
\!patent
 US
Patent 5564004 uses Voronoi diagrams as part of a user interface
that highlights the icon nearest the cursor in a windowing system.
\
\!graphics
\!patent
 US
Patent 5574835 describes a method of performing visibility checking
of polygons by intersecting bounding boxes.
\
usenet
\!typography
\!index
 Usenet messages by Chuck Bigelow and others
discussing algorithms for automatic kerning.
\
using
\!typography
\!vision
\!voronoi
 Using the
Voronoi Tessellation for Grouping Words and Multipart Symbols in
Documents, M. Burge and G. Monagan.
\
vclip
\!vreal
 The VClip
collision detection library for exact collision detection between
nonconvex polyhedra (intended for use after bounding boxes or other
methods have been used to reduce the set of possible collisions).
\
virtual
\!medial
\!arch
 Virtual terrain
project: Roofs.
\
visualization
\!interpolate
 Visualization of three different interpolation methods: knearest neighbors, natural neighbors, and gammaobservable neighbors. Java applet by Michaël Aupetit.
\
visualizing 3d
\!delaunay
\!sci
 Visualizing 3D spatial patterns of archaeological assemblages.
Diego Jiminez and Dave Chapman use betaskeletons and other Delaunaylike proximity graphs
to find potential semantic connections between Mexican artifacts.
\
visualising the structure of architectural
\!arch
\!recent
\# 17 Jun 2004
 Visualising
the structure of architectural open spaces based on shape analysis.
Sanjay Rana and Mike Batty use a simple greedy visibility calculation to
find lines of visibility for both building floorplans and urban areas.
\
visualizing the structure of the www
\!gdraw
\!vreal

Visualizing the structure of the WWW in hyperbolic space,
T. Munzner and P. Burchard. Hyperbolic graph drawings and
flythroughs.
\
volume
\#interpolate
\#cad
 Volume
and surface reconstruction of complex 3d objects from scattered points
on the boundary for CAD/CAM applications
\
voronoi
\!voronoi
 Voronoi.com, tutorials,
applications, and implementations of Voronoi methods of spatial
analysis.
\
voronoi
\!voronoi
 Voronoi,
Dutchlanguage web site dealing with Voronoi diagrams.
\
voronoi art
\!voronoi
 Voronoi Art.
Scott Sona Snibbe uses a retroreflective floor to display the Voronoi
diagram of people walking on it, exploring notions of personal space and
individualgroup relations.
Additional Voronoibased art is included in his
dynamic
systems series.
\
voronoi diagram of mcd's
\!voronoi
\!carto
 Voronoi diagram
of McDonalds outlets in San Francisco.
Demo of a commercial GIS tool.
\
voronoi diagrams from arch
\!voronoi
\!index
 Voronoi diagrams: from
archaeology to zoology. Lecture by Scot Drysdale.
\!index
Mentions applications in anthropology, archaelogy, astronomy,
biology, ecology, forestry, cartography, crystallography, chemistry,
finite element analysis, geography, geology, geometric modeling,
marketing, mathematics, metallurgy, meteorology, pattern recognition,
physiology, robotics, statistics, and zoology.
\!index
\
voronoi diagrams in bio
\!voronoi
\!bio
 Voronoi
diagrams in biology, Zdravko Jeremic, Benoit College.
\
voronoi methods
\!voronoi
\!carto
\!index
 Voronoi methods in geomatics.
Abstract of a talk by Chris Gold at Carleton U.
See also
Gold's
many papers on Voronoidiagram based methods in geographic
information systems.
\
wau
\!carto
 R. Waupotitsch has implemented various
optimal
triangulation algorithms as part of the
GRASS
geographic resources analysis support system.
\
weather
\!sci
\!mst
 Weather
data interpretation. The Insight group at Ohio State is using
geometric techniques such as minimum spanning trees to extract features
from large meteorological data sets.
\
well separated
\!quadtree
\!astro
\!molmod
 The
WellSeparated Pair Decomposition and its Applications,
Paul Callahan's Johns Hopkins Ph.D. thesis
on hierarchical space decomposition
and its applications to nbody simulation.
\
wignerseitz
\!voronoi
\!metal
 The
WignerSeitz method for modeling electron flow in metals
by using Voronoi cells of the crystal lattice.
\
wise
\!arch
\!telecom
 The WISE
wireless system engineering tool uses computational geometry
techniques developed by Steve Fortune of Bell Labs as part of a package
for predicting signal propagation of radio links inside buildings.
More information on the geometric problems arising here can be found
in Steve's paper "A beam tracing algorithm for prediction of indoor
radio propagation", in the 1st ACM Worksh. on Applied Computational Geometry.
\
worksh. alg.
\!conf
\!robot
 Worksh. Algorithmic Foundations of Robotics.
1st Worksh., proceedings contents and ordering info.
3rd Worksh.,
Houston, March 1998, program and participants.
\
www
\!arch
 WWW Virtual Library: Architecture
\
yahoo
\!medic
 Yahoo
directory of Medical Imaging resources.
\
yahoo
\!textile
 Yahoo directory of textile software vendors
\
yahoo
\!vision
 Yahoo directory of Computer Vision resources.
\
z
\!geom
 Other collections of geometry web pointers:
O. Aichholzer.
H. Choset.
L. Cusick.
J. Erickson.
J.A. Ferrez
S. HarPeled.
A. Hausner.
S. Llywellynne.
E. Mücke.
A. Natowitz.
G. A. Pinto.
S. Pemmaraju.
R. Salgado.
M. Woodcock.
Carleton U.
EINet Galaxy.
FernU. Hagen.
Links2go.
U. Tennessee.
Yahoo: Geometry.
Yahoo: Computational Geometry.
\
\+