*"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
MacHale, Comic
Sections(Dublin 1993)

**" 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 |
Compilers |
Operating Systems |
Graph Theory

Computer Science |
Engineering/Technology |
Java | Parallel Computing

Computational Geometry Lecture Notes

- Introduction
- Polygon Partitioning
- Convex Hull
- Voronoi Diagram
- Delaunay Triangulation
- Proximity Problem
- Reporting Intersection of a Set of Half Planes
- Convex Polygon Decomposition
- Famous
NP-Complete Problems in Computational Geometry
- TSP Heuristic Algorithm
- TSP Heuristic Algorithm (when end point differs from start point)
- TSP Algorithm (when start point is given and end point is arbitrary)
- TSP Heuristic Algorithm (when start point and end point are given)
- Steiner Tree Problem's Heuristic Algorithm with Minimum Spanning Tree Problem

- Appendix
- Algorithms Illustration (Applet) from "Computational Geometry in C" by J. O'Rourke

Computational Geometry
Notes by Professor Jianer Chen

Geometry Center
-- Center for the Computation and Visualization of Geometric Structures.

History
of Geometry

History of Mathematics Archive

Euclid's Element

Introduction to the Works of Euclid

- Ipe extendible drawing editor -- Geometric drawing editor for creating figures for inclusion into LaTeX documents.
- RobustPredicates -- Orientation and in circle tests.
- Real/Expr -- is a set of C++ class libraries which supports the precision-driven approach to implementation of exact algorithms in computational geometry.
- Determinant Sign Software -- 2-by-2 and 3-by-3 determinants.

Simulation of Simplicity -- Symbolic Perturbation

Toolkit for Algebra and Geometry (ftp) -- Multivariate polynomial Intersection, Sturm-Habicht sequences, Resultants.

Polynomial Solver (Sparse resultant software) -- Multivariate Polynomial Intersection, Resultants.

- LEDA -- Library of Efficient Data-types and Algorithms, planar geometric objects, graph algorithms.
- The LEDA Platform of Combinatorial and Geometric Computing by K. Mehlhorn and St. Näher -- A book by creators of LEDA.
- The LEDA Tutorial by Joachim Ziegler

- XYZ Geobench (ftp): --platform: Mac, Object Pascal.
- Geolab(ftp): -- Platform: Sun, C++. Requires the Sun C++ Compiler.

- hull -- Incremental algorithm. Resolves degeneracies lexicographically. Optional Randomization. Outputs include VD, DT, Volume of Voronoi faces, and alpha shapes. .. etc.
- lrs (ftp) -- pivoting paradigm. Half-space Intersection (deterministic transversal), resolve degeneracies lexicographically, compute volume.
- chD (ftp) -- Incremental algorithm. Uses symbolic perturbation. Computes volume.

- Detri -- Flipping paradigm. Robust 3D Delaunay. Uses symbolic perturbation for degeneracies.
- tess(ftp, tar.Z) -- Gift-wrapping paradigm. 3D Delaunay attention to numerical stability of predicates.
- Delaunay Tree Program -- Incremental algorithm. Semi-dynamic 2D and 3DDelaunay triangulation.
- J.O'Rourke - Computational Geometry in C (ftp) -- Incremental algorithm.3D CH.

- S.Fortune - 2D Voronoi/Delaunay -- Sweepline algorithm.
- Triangle (A Two-Dimensional Quality Mesh Generator and Delaunay Triangulator) -- Incremental algorithm. Divide-and-Conquer paradigm.
- 2DVoronoi/Delaunay (ftp) -- Incremental Delaunay Triangulation, Graphics Gems IV.
- 2D Convex Hull (ftp)
-- Graham's scan
algorithm. J. O'Rourke, Computational Geometry in C.

2D Convex Hull (LEDA) -- Incremental algorithm.

- Constrained Delaunay Triangulation -- Flipping algorithm.
- Fast Polygon Triangulation (Graphics Gems V, ftp) -- Graphics Gem. Seidel's O(nlogn) algorithm for simple polygons (ext. polygon with holes).
- Simple Polygon Trapezoidation (ftp, tar.Z) -- Seidel's algorithm for simple polygons.
- Super Delaunay Triangulation Library -- Fast & fully constrained Delaunay Triangulation.
- Arrangement Trapezoidation (ftp) -- Randomized incremental trapex of arrangement of polygons in the plane or on the sphere.
- Terrain Triangulation -- Greedy incremental algorithm for approximation of dense point data.

- Triangle -- Delaunay refinement. Ruppert's algorithm.
- Tripoint (ftp) -- Quad-tree. Mitchell's algorithm for meshes. MATLAB interface.
- Meshing code in SimLab, Cornell U. -- a Delaunay refinement. Chew's algorithm. Handles curved boundaries. Built on algebraic and topological computation system.

- QMG,Cornell U. -- Quad-tree.

- Point in polygon test (Point in Polygon Strategies, ftp)
- Point in polygon test (ftp) -- J. O'Rourke, Computational Geometry in C.
- Planar point location (ftp)
- Boolean Operations (clippoly)
- Line Segment Intersection (LEDA)
- Visibility Graph (VisPak) -- Collection of visibility graphs, visibility polygons, and axis-aligned polygons programs.

- Linear Programming Program (lp) -- Implementations of Seidel's and Clarkson's algorithms.

- 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.
- AlphaShapes (Hull) -- Computes alpha shapes in any dimension. Handles degeneracy.
- k-nearest neighbors (Ranger) -- Space decomposition algorithms. Does orthogonal range queries.

- Bibliography -- Search in the Computational Geometry at Technical U. of Catalonia, Spain.
- Computational Bibliography Search -- Mcgill U.
- Computational Geometry at arXiv.org e-Print archive
- Geometry Algorithms Journals at Geometry Algorithms
- Search Geometry Literature Database -- Utrecht U., Netherlands.

- Computational Geometry: Algorithms
and Applications by Mark de Berg, Otfried
Schwarzkopf, Marc van Kreveld and Mark Overmars
- Introduction or chapter 7 on Voronoi diagrams available.

- Computational Geometry Books
- Computational Geometry Books at Geometry.net
- Franz Aurenhammer's Publications
- Geometry Algorithms Textbooks
- Handbook of Computational Geometry
- LEDA Platform of Combinatorial and Geometric Computing by K. Mehlhorn and St. Näher -- ps-files of some chapters available.

- Application Challenges to Computational Geometry - Summary by Jeff Erickson -- Computational Geometry Impact Task Force Report, chaired by Bernard Chazelle, about the relation 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 Computational Geometry -- Section of the Computing Research Repository (CoRR), moderated by Joseph O'Rourke.
- CGAL -- Computational Geometry Algorithms Library (in C++)
- CGAL Demo Programs -- screen shots from various demonstration programs for CGAL with source codes.
- Compgeom Mailing Lists -- Three mailing lists for announcements, discussion, and (inactive) tribune about computational geometry.
- Computational Geometry in C by Joseph O'Rourke
- Computational Geometry Demos
- Computational Geometry Interactive Software
- Computational Geometry Pages -- Jeff Erickson's comprehensive directory of computational geometry resources, including bibliographies, journals, software, and related hubs.
- Computational Geometry Programs & Packages
- Computational Geometers
- Delaunay Triangulation
- Frequently 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 triangulation.
- Geometry Algorithms -- Resources for geometry algorithm software: monthly algorithm and archive, books and journals, related web links, and a short history of geometry.
- Geometry Center
- Geometry in Action
- Geometry Junk Yard
- Geometry Lab - Computer Science Dept, U. of Bonn
- Geometry Literature Database (geombib) -- An ongoing project compiling a reasonably complete BibTeX bibliography of papers in computational geometry.
- 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.
- Graham's Scan
- Java demos of some computational geometry algorithms
- Jiri Matousek's Lecture Notes
- Laurent Balmelli's homesite -- Laurent Balmelli is a research staff member at the IBM T.J. Watson Center in Hawthorne, NY. His main interests and fields of research are computational geometry, digital geometry processing, data compression, data structures and optimization techniques. This site contains his recent publications, as well as demos and software.
- LEDA - Extension Package at Algorithmic Solutions Software GmbH
- Mathtools.net --The technical computing portal for all scientific & engineering needs.
- Netlib -- collection of mathematical software, papers, and databases.
- Open Problems on Computational Geometry
- Open Problems on Geometry
- Strategic Directions in 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 areas.
- Single Purpose Algorithm Visualization
- Stony Brook Algorithm Repository: -- Implementation in C, C++, Pascal and Fortran.
- Scientific Graphics Project -- Publications and software. Hosted by MSRI.
- Voroglide
- Voronoi Diagrams -- Selected references and links.
- Voronoi Web Site, The

- Computational Geometry Research Groups
- MSRI - Mathematical Science Research Institute -- exists to further mathematical research through broadly based programs in the mathematical sciences and closely related activities.

- Caltech Multi-Res Modeling Group -- Conducts research into the mathematical and algorithmic foundations of numerical problems in computer graphics and scientific computing with a specific focus upon multiresolution techniques.
- Computer Graphics Group -- Friedrich Alexander University of Erlangen-Nuremberg. Research areas include modeling, rendering, and scientific visualization.
- Computer Graphics Laboratory -- Stanford University. Research areas include volume rendering, rendering algorithms and systems, 3D scanning, image-based rendering, virtual reality, compression of graphics objects, user interfaces for visualization, high-performance graphics architectures, and visualization of complex systems and environments.
- Computer Graphics On-Line Notes at UC. Davis
- Geometric 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.

- 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.
- Graphviz -- open source graph drawing software at AT&T.
- GDToolkit -- LEDA-based library of C++ classes for graph drawing.
- 3DCube -- tool for 3D graph drawing.

- ACM Annual Symposium on Computational Geometry -- Electronic proceedings from 1987 and onwards.
- ACM Workshop on Applied Computational Geometry WACG'96
- Canadian Conference on Computational Geometry (CCCG) -- Electronic Proceedings available for download from 1997 and onwards.

**There is no place
like
Home**