"The book of nature is written in the characters of geometry." - Galileo

Go to Specific Links Related to COMP-507 (Computational Geometry course).

General Links - Computational Geometry:

• Geometryalgorithms.com ( Fantastic Resource Page for Computational Geometry!)
• Jeff Erickson's Computational Geometry Pages
• Geometry in Action
• Geometry Publications by Author
• Godfried's Research Interests in Computational Geometry
• A Gallery of JAVA Sketchpad Examples in Constructive Geometry
• Software:
• JeoEdit - A Java tool for editing polygons and points on the web
• Directory of Computational Geometry Software
• CGAL Computational Geometry Library
• Algorithmic Solutions.Com
• Computational Geometry Courses and Teaching Materials
• David Mount's Course Notes
• Robert Pless's Course
• Computational Geometry Course at Brown University
• Computational Geometry 201 (Australia)
• Ken Clarkson's Course
• Algorithm Animations
• Basic Introduction to Computational Geometry (PostScript file)
• Godfried's Favourite Computational Geometry Links
• Computational Geometry on the Web
• Computational Geometry in Barcelona
• Computational Geometry Links
• Computational Geometry Applications
• Computational Geometry (Wolfram Research)
• Some Computational Geometry Algorithms
• Computational Geometry Algorithms Library
• Center for Geometric Computing
• Geometry Center
• Open Problems
• Qhull Home Page
• 3-D Models
• Technology in the Geometry Classroom

General Links - More Geometry:

• Experiencing Geometry (A really nice basic geometry course by David Henderson)
• Geometry and the Imagination
• Geometry from Euclid to Today
• General Geometric References
• Geometry Formulas and Facts
• Interactive Geometry
• Interactive Geometry Miscellany
• Miscellaneous Topics in Geometry
• My Favorite Geometry Links on the Web
• Open Problems in Discrete and Computational Geometry
• Polygons
• Polyhedra
• Tessellations
• Geometric Probability

Specific Links Related to the Course Material:

Chapter Links:

1. Classical Geometry, Basic Concepts, Theorems and Proofs
2. Point Inclusion Problems
3. Convexity Testing
4. Polygon Triangulation
5. Art-Gallery Theorems
6. Polygonizations of Point Sets and Generating Random Polygons
7. Distances Within and Between Sets
8. Subdivisions Induced by Points: Triangulations, Quadrangulations...
9. Complexity, Convexity and Unimodality
10. Convex Hulls
11. Visibility (Hidden-Line Problems)
12. Updating Triangulations of Points and Line Segments
13. Intersection Problems
14. Proximity Graphs, Voronoi Diagrams and Polyhedral Computations
15. Linear Programming
16. Facility Location
17. Mobility of Objects in Space
18. Degeneracies in Computational Geometry
19. Transversals of Sets
20. Arrangements
21. Skeletons of Polygons
22. Visualization

1. Classical Geometry, Basic Concepts, Theorems and Proofs

1. The Straight-Edge and Compass Computer:
1. Francois Labelle's Tutorial on the Complexity of Ruler and Compass Constructions (with interactive Java applet)
2. GRACE (A graphical ruler and compass editor)
3. The straight-edge and compass
4. Constructive geometry of the Greeks
5. Geometric constructions
6. Geometrography and the Lemoine simplicity of geometric constructions
2. Wonders of Ancient Greek Geometry
3. Models of Computation:
1. Ceiling and Floor functions
4. Polygons and representations
5. Computing the area of a polygon
6. On Proving Things:
1. Notes on methods of proof
2. 100% Mathematical Proof
3. The Nuts and Bolts of Proofs
4. Writing Down Proofs
5. On Proofs in Mathematics
6. Imre Lakatos on Proofs and Refutations
7. More about Imre Lakatos
8. Common errors in mathematics

1. The Jordan Curve Theorem:
1. Octavian Cismasu's Tutorial on the Jordan Curve Theorem (with interactive Java applet)
2. Point-in-Polygon Testing:
1. The plumb-line algorithm
2. More on the plumb-line algorithm
3. Point inclusion in the query mode

1. Convex Polygons:
• On the number of diagonals in a convex polygon (with interactive Java applet)
2. Testing the orientation of a simple polygon
3. Testing the convexity of a polygon

1. History of Triangulation Algorithms
2. Ears and Mouths of Polygons:
1. Ian Garton's Tutorial on cutting ears and stuffing mouths (with interactive Java applets)
2. Simple polygons have ears and mouths
3. Meisters' Two-Ears Theorem
1. More about Gary Meisters
4. The one-mouth theorem:
1. Ian Garton's Tutorial
2. Polygons are Anthropomorphic (PostScript file)
3. Diagonal insertion
4. Prune-and-Search:
1. Finding an ear in linear time (PostScript)
2. Finding an ear in linear time (HTML)
5. The Graham Scan triangulates simple polygons (PostScript)
6. Fast Polygon Triangulation in Practice:
1. Efficient polygon triangulation algorithms. Includes counter-examples to many published algorithms. (PostScript)
2. Geometric hashing for faster Ear-Cutting in practice (PostScript)
7. Seidel's Algorithm
8. Triangulating monotone polygons in linear time
9. Diagonals: Part I - AMS Feature Column Essay by Joseph Malkevitch

1. The Art-Gallery problem:
1. Chvatal's art gallery theorem
2. Thierry Dagnino's Tutorial on Chvatal's art-gallery theorem (with interactive Java applet)
2. Three-colorability of triangulated polygons
3. Illuminating the Free Space Among Quadrilateral Obstacles
4. Mobile (edge) guards
5. Illuninating polygons with mirrored walls

1. Drawing Simple Polygons through Sets of Points:
1. Tony Ruso & Valeriu Sitaru's Polygonization Tutorial (with interactive Java applet)
2. Monotonic polygonizations
3. Star-shaped polygonizations
2. Polygonization counter (Java applet)
3. Generating Random Polygons
4. Midpoint Polygonization of Points (with Java applet)

1. Minkowski metrics
1. Distance
2. Manhattan metric: Pascal Tesson's tutorial on taxicab geometry
2. Minkowski Operations:
1. Minkowski sum and difference
2. Software for computing Minkowski sums
3. More about Hermann Minkowski
4. The Closest Pair Problem:
1. Closest-pair applet animation of divide-and-conquer algorithm
5. Diameter algorithms:
1. Diameter algorithms (Mathew Suderman's tutorial)
6. Computing the Width of a Set:
1. Jaqueline Chen's tutorial on width (with interactive Java applet)
2. Width algorithms in 2 and 3 dimensions (PostScript file)
7. The Rotating Calipers
1. The Rotating Caliper Page of Hormoz Pirzadeh (with an awsome Java applet!)
2. Solving five geometry problems with the rotating calipers
3. The Rotating Caliper Graph
4. The Reuleaux triangle (Eric's Treasure Trove)
5. The Reuleaux triangle (The Geometry Junkyard)
6. Shapes of Constant Width
8. The Maximum Distance:
1. A simple O(n log n) algorithm for computing the maximum distance between two finite sets in the plane (PostScript)
2. A more complicated O(n log n) algorithm for the maximum distance between two point sets which generalizes to higher dimensions (PostScript)
9. The Minimum Distance:
1. The minimum distance between two point sets (PostScript)
2. The minimum vertex distance between two convex polygons (PostScript)
10. The Hausdorff Distance:
1. The Hausdorff Distance
2. Normand Gregoire & Mikael Bouillot's Tutorial on the Hausdorff distance and its applications (with interactive Java applet)

1. Triangulations:
1. Triangles
2. Triangulation via Polygonizations of points
3. Divide-and-conquer
4. The three-coins algorithm
5. Monotone polygons
6. Star-shaped polygons
7. Edge-visible polygons
8. Externally visible polygons
2. Minimum-Weight Triangulations:
1. Francois Labelle's interactive Java applet
2. Minimum-weight triangulation of a convex polygon
3. Quadrangulations:
1. Quadrilaterals
2. Martin Blais' Tutorial on Quadrangulations (with interactive Java applet)
3. Characterizing and Computing Quadrangulations of point sets (PostScript file)
4. Converting triangulations to quadrangulations (PostScript file)
5. Application of convex quadrangulations to font design

1. Convex Set, convex function
2. Unimodal distance functions in geometry
3. Binary Search

1. Convex hull algorithms for points in the plane (Java interactive demos)
1. Convex hulls in 2 and 3 dimensions (interactive Java demos)
1. Incremental (point-insertion)
1. Randomized incremental (PostScript)
2. The Graham scan
1. More about Ron Graham
3. Divide & Conquer (merge hull)
4. Quickhull (throw-away principle)
5. The Jarvis march (gift-wrapping)
6. Chan's Algorithm
1. More about Timothy Chan
7. Kirkpatrick-Seidel's ultimate algorithm (PostScript)
1. More about David Kirkpatrick
2. Qhull Home Page
2. Convex hulls and duality
3. Linear expected time algorithms
1. Via Bucket-Sorting and Floor Functions (compressed PostScript file)
2. The throw-away principle (PostScript)
3. A fast convex hull algorithm - Algorithm of Akl and Toussaint (PDF file)
4. Convex hull algorithms for polygons:
1. 3-Coins Algorithm Tutorial (Greg Aloupis and Bohdan Kaluzny)
2. Melkman's linear-time algorithm (Pierre Lang's tutorial with Java applet)
3. Another tutorial on Melkman's algorithm
4. A History of Linear-time Convex Hull Algorithms for Simple Polygons - by Greg Aloupis

1. Visibility from a point
2. Visibility from an edge (PostScript)
3. Visibility from a line
4. Visibility Graphs
1. Computing visibility graphs of line segments and polygons

1. Updating Triangulations:
1. Sergei Sauchenko's Tutorial on inserting and deleting vertices and edges from triangulations (with interactive Java applets)

1. Intersecting convex polygons:
1. Slab method of Shamos and Hoey
1. More about Michael Shamos
2. Eric Plante's Tutorial on the Rotating-Caliper method (with interactive Java applet)
3. A simple linear algorithm for intersecting convex polygons (Rotating Caliper method) (PostScript file)
2. Intersecting half-planes
3. Intersecting simple polygons
4. Applications
1. Linear Programming
2. Voronoi diagrams
3. Kernel of a polygon

1. Minimum spanning trees
2. Nearest neighbour graphs
3. The Relative Neighbourhood Graph (PostScript)
1. Lune (also vescica piscis or lens)
4. The Gabriel graph
5. The Delaunay triangulation
1. Delaunay Triangulations for Spatial Modelling
2. Finding 2-D Delaunay Trinagulations from 3-D Convex Hulls (interactive Java applet)
3. Comparison of Delaunay TrinagulationAlgorithms
4. Computing Constrained Delaunay Trinagulations in the Plane
6. Voronoi Diagrams:
1. The Voronoi Web Site (Christopher Gold)
2. VoroGlide (fantastic interactive Java applet for Voronoi diagrams and Delaunay triangulations)
3. Another interactive applet for delaunay triangulations and Voronoi diagrams
4. A Voronoi vertex is the circumcenter of its Delaunay triangle
5. David Eppstein's Links for Voronoi diagrams and applications
6. Voronoi Implementation (great applets!!!)
7. Tutorial on Fortune's Voronoi Diagram Algorithm
8. Higher-Order Voronoi Diagram Applet
7. Applications of Voronoi Diagrams:
1. Mark Grundland's Fractals from Voronoi diagrams
8. Sphere of influence graphs (SIG's)
1. Richard Unger's tutorial on SIG's (with interactive Java applet)
9. Proximity Graphs (including a survey paper)
10. Alpha Shapes and Beta Skeletons:
11. Alpha shapes
1. François Bélair's Tutorial on Alpha Shapes (with interactive Java applet and a super-duper automated guided-tour demo)
2. Gallery of alpha shapes
3. Code for computing alpha-shapes (and convex hulls)
12. Beta skeletons:
1. Xiaoming Zhong's Tutorial on Beta Skeletons (with interactive Java applet)
13. Polyhedral Computation:
1. Frequently Asked Questions in Polyhedral Computation (by Komei Fukuda)

1. What is Linear Programming?
2. Introduction to Linear Programming
3. Interactive Linear Programming
4. The Simplex Algorithm (Java Applet)
5. Linear programming problems in geometry
6. Megiddo's linear time algorithm
1. Geometric Series
2. Prune-and-Search Algorithm Applet

1. The minimax facility location problem
2. The smallest enclosing circle:
1. An O(n log n) algorithm (with interactive Java applet)
2. Smallest Enclosing Ball Code
3. C++ Code for Smallest Enclosing Balls in all Dimensions
4. The linear time algorithm of Megiddo and Dyer (Tutorial of Jacob Eliosoff and Richard Unger with applet)
3. Generalizations to geodesic metrics
4. Constrained facility location problems in the plane and on the sphere
5. A survey of geometric facility location problems

1. The Match-Stick Game: Fabienne Lathuliere's Tutorial on Translation Separability of Sets of Line Segments (with interactive Java applet)
2. Translation separability of objects (compressed PostScript file)
1. Separating objects in space (Tutorial by Kishore Anand and Anatoly Lichatchev with EXPLOSIVE applet!)interactive 4-bar linkage applet
2. The Rhombic Dodecahedron
3. Separating Two Monotone Polygons in Linear Time
4. Separating Two Simple Polygons via Relative Convex Hulls
5. Geodesic Paths:
1. Geodesic (relative) convex hulls
2. Steve Robbins' Tutorial on Relative Convex Hulls
3. Shortest-paths for robotics planning (with Java applet)
4. The algorithm of Chazelle and Lee-Preparata
6. Linkages
1. A historical introduction to linkages by Joseph Malkevitch
2. Interactive 4-bar linkage applet
3. Planar Machines' web site. An invitation to Topology. (multiple link linkages! fantastic site!!!)
4. Paucellier's Linkage
7. Convexifying Polygons:
1. Linda Sun's tutorial on generating self-avoiding polygons

1. General position assumptions
2. What is a degeneracy?
3. Some examples of geometric degeneracies
4. Robustness
5. An arithmetic for handling intrinsic degeneracies
6. Lower bounds for detecting affine and spherical degeneracies
7. Avoiding Algorithm-Induced Degeneracies: (PostScript)
1. No two points on a vertical line
2. No three points on a vertical plane
3. No two points with the same coordinates
4. and many many more
8. Computing nice viewpoints of objects in space (PostScript)

19. Transversals of Sets

1. The Philo Line (Philo of Byzantium):
1. Definition and computation
2. Historical survey and characterizations
2. Point-line duality:
1. Interactive Java demos illustrating various definitions of duality
3. The space of transversals
4. Computing shortest transversals

20. Arrangements

1. Arrangements of lines
1. Envelopes of Arrangements of Lines (compressed PostScript file)
2. Arrangements of line segments
3. Arrangements of discs
4. Arrangements of Jordan curves

21. Skeletons of Polygons

1. The medial axis
2. The Straight-Line skeleton

22. Visualization

1. Nice Projections:
1. Map projections
2. Regular Projections and Knot Theory
2. Aperture-Angle Optimization Problems:
1. Viewing a statue
1. Applet for aperture angle demo
1. The Spindle Torus
2. Kepler's Apples and Lemons
3. More about Kepler
4. Aperture-angle optimization problems in two dimensions (PostScript)
5. Aperture-angle optimization problems in three dimensions (PostScript)

Teaching Activities Homepage