Computational Geometry Lecture Notes

1. Introduction
   • Definitions
   • Two-Ears Theorem
2. Polygon Partitioning
3. Convex Hull
   • Incremental
     • Higher Order Convex Hull
   • Graham's Scan
   • Jarvis March
   • Quick Hull
4. Voronoi Diagram
   • Incremental Method
   • Plain Sweep Method
   • Divide-and-Conquer Method
5. Delaunay Triangulation
• Delaunay Tessellation 
• Second Order Delaunay Tessellation 
• Third Order Delaunay Tessellation
6. Proximity Problem
   • Planar Ordinary Voronoi Diagram 
   • Area of Voronoi Region  
   • Higher Order Voronoi  
   • Voronoi Diagram with the Minkowski metric L_p
     • Manhattan Voronoi 
     • Higher Order Manhattan Voronoi 
     • Supermum Voronoi 
     • Higher Order Supremum Voronoi 
     • Karlsruhe Voronoi
     • Higher Order Karlsruhe Voronoi 
     • Largest Empty Circle Problem
     • Smallest Enclosing Circle Problem
     • Nearest Point, Farthest Point Pair
7. Reporting Intersection of a Set of Half Planes
8. Convex Polygon Decomposition
9. 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
10. 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

Arithmetic Tools

• 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.

Objects and Data Structures

• 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

Environments

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

Arbitrary-Dimensional Convex Hull & Programs

• 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.

3-Dimensional VoronoiDiagram (VD), Delunay Triangulation (DT), and Convex Hull (CH)

• 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.

2-Dimensional Voronoi Diagram, Delunay Triangulation, and Convex Hull

• 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.

2-Dimensional Triangulation and Trapezoidation

• 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.

2-Dimensional Mesh Generation

• 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.

3-Dimensional Mesh Generation

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

Problems on Polygons

• 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.

LP-Type Problems

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

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

Bibliography Search

• 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.

Books and Online papers

• 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.

Links

• 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
  • Directory of Computational Geometry Software by Nina Amenta
• 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

Groups

• 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.

Graphics Links in Computational Geometry

• 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.

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.
• 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.

Conferences, Workshops & Symposiums

• 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.