"Analytical geometry has never existed. There are only people
who do linear
geometry badly, by taking coordinates, and they call this analytical
geometry. Out with
them!"- Jean Dieudonné
"The first test of potential in mathematics
is whether you can get anything out of geometry." Quoted in D
"The significant problems we face cannot be solved at the same
level of thinking we were at when we created them." - Einstein
Algorithms | Computer Architecture |
Operating Systems |
Computer Science |
Java | Parallel Computing
Computational Geometry Lecture Notes
Reporting Intersection of a
Set of Half Planes
NP-Complete Problems in Computational Geometry
- Convex Hull
- Voronoi Diagram
- Delaunay Triangulation
Notes by Professor Jianer Chen
-- Center for the Computation and Visualization of Geometric Structures.
History of Mathematics Archive
Introduction to the Works of Euclid
Objects and Data Structures
Arbitrary-Dimensional Convex Hull &
Incremental algorithm. Resolves degeneracies lexicographically.
Optional Randomization. Outputs
include VD, DT, Volume of Voronoi faces, and alpha shapes. ..
lrs (ftp) --
Half-space Intersection (deterministic transversal), resolve
degeneracies lexicographically, compute
algorithm. Uses symbolic perturbation. Computes volume.
3-Dimensional VoronoiDiagram (VD),
Delunay Triangulation (DT), and Convex Hull (CH)
2-Dimensional Voronoi Diagram, Delunay
Triangulation, and Convex Hull
2-Dimensional Triangulation and
- Triangle --
- Tripoint (ftp) --
Quad-tree. Mitchell's algorithm for meshes. MATLAB interface.
code in SimLab, Cornell U. -- a Delaunay
refinement. Chew's algorithm. Handles
curved boundaries. Built on algebraic and topological computation
3-Dimensional Mesh Generation
Problems on Polygons
Point Set Problems
- Alpha Shapes Software
-- Package to generate, display, compute volume, surface area of
weighed or un-weighted of 2D and 3D alpha
shapes. Finds and measures holes, pockets and voids. Handles degeneracy.
(Hull) -- Computes alpha shapes in any dimension.
neighbors (Ranger) -- Space decomposition algorithms.
Does orthogonal range
Books and Online papers
to Computational Geometry - Summary by Jeff Erickson --
Geometry Impact Task Force Report, chaired by Bernard Chazelle, about
between computational geometry and various application fields. This
page also archives
the discussion that it caused (which was intended) and related links.
- Algorithmic Solutions
Software formerly LEDA -- Library of Efficient Data-types
and Algorithms (in C++).
- ArXiv: cs.CG
Geometry -- Section of the Computing Research
moderated by Joseph O'Rourke.
- CGAL -- Computational Geometry
- CGAL Demo Programs --
screen shots from various demonstration programs for CGAL with source
Lists -- Three mailing lists for announcements,
(inactive) tribune about computational geometry.
Geometry in C by Joseph
Pages -- Jeff Erickson's comprehensive directory of
geometry resources, including bibliographies, journals, software, and
Geometry Programs &
Asked Questions in Polyhedral Computation at Swiss Federal Institute of
Technology, Switzerland -- Notes related to convex
hull computation of a finite point set, the vertex enumeration for a
convex poly-type, the computation of Voronoi diagram and Delaunay
- Geometry Algorithms --
geometry algorithm software: monthly algorithm and archive, books and
web links, and a short history of geometry.
- Geometry Center
- Geometry Lab -
Computer Science Dept, U. of Bonn
Literature Database (geombib) -- An ongoing project
reasonably complete BibTeX bibliography of papers in computational
- GeomNet: Geometric
Computing over the net by Gill Barequet, Stina S. Bridgeman,
Christian A. Duncan, Michael T. Goodrich, and Roberto Tamassia.
- Gishur Project, The
-- platform independent, object oriented, flexible and efficient
framework to implement and visualize geometric algorithms.
- Java demos of some
computational geometry algorithms
Matousek's Lecture Notes
homesite -- Laurent Balmelli is a research staff member
at the IBM T.J.
Watson Center in Hawthorne, NY. His main interests and fields of
computational geometry, digital geometry processing, data compression,
and optimization techniques. This site contains his recent
publications, as well as demos
- LEDA -
Extension Package at Algorithmic
Solutions Software GmbH
- Mathtools.net --The
computing portal for all scientific & engineering needs.
-- collection of mathematical software,
papers, and databases.
- Open Problems on
Computational Geometry -- ACM/NSF Working Group Report
chaired by Roberto
Tamassia, intended to complement the Application Challenges to
Computational Geometry by
suggesting overall research directions instead of specific problem
- Stony Brook
Repository: -- Implementation in C, C++, Pascal and
Graphics Project -- Publications and software. Hosted
- Voronoi Diagrams --
Selected references and links.
Graphics Links in Computational Geometry
- Caltech Multi-Res Modeling Group --
Conducts research into the mathematical and algorithmic foundations of
problems in computer graphics and scientific computing with a specific
- Computer Graphics Group --
Friedrich Alexander University of Erlangen-Nuremberg. Research areas
rendering, and scientific visualization.
- Computer Graphics Laboratory --
Stanford University. Research areas include volume rendering, rendering
systems, 3D scanning, image-based rendering, virtual reality,
compression of graphics
objects, user interfaces for visualization, high-performance graphics
and visualization of complex systems and environments.
Computer Graphics On-Line Notes at UC. Davis
Modeling On-Line Notes at UC. Davis
Graph Drawing Tutorial (pdf) by Isabel F. Cruz
and Roberto Tamassia
- Graph Theory and its Applications
-- comprehensive graph theory resource for graph
theoreticians and students.
Software Libraries and Tools for Graph Drawing
- AGD -- LEDA-based
library of C++ classes for graph drawing.
- aiSee -- graph drawing
tool that supports a variety of layout methods.
- Graph Drawing Server
-- Web-based graph drawing service.
-- open source graph drawing software at AT&T.
- GDToolkit --
LEDA-based library of C++ classes for graph drawing.
-- tool for 3D graph drawing.
Conferences, Workshops & Symposiums
There is no place