 "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 - More Geometry: Specific Links Related to the Course Material: 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:
4. Polygons and representations
5. Computing the area of a polygon
6. On Proving Things:
2. Point Inclusion Problems
1. The Jordan Curve Theorem:
1. Octavian Cismasu's Tutorial on the Jordan Curve Theorem (with interactive Java applet)
2. Point-in-Polygon Testing:
3. Point inclusion in the query mode
3. Convexity Testing
1. Convex Polygons:
2. Testing the orientation of a simple polygon
3. Testing the convexity of a polygon
4. Polygon Triangulation
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
4. The one-mouth theorem:
3. Diagonal insertion
4. Prune-and-Search:
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
5. Art-Gallery Theorems
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
6. Polygonizations of Point Sets and Generating Random Polygons
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)
7. Distances Within and Between Sets
1. Minkowski metrics
2. Minkowski Operations:
4. The Closest Pair Problem:
5. Diameter algorithms:
6. Computing the Width of a Set:
7. The Rotating Calipers
8. The Maximum Distance:
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)
8. Subdivisions Induced by Points: Triangulations, Quadrangulations...
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:
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
9. Complexity, Convexity and Unimodality
1. Convex Set, convex function
2. Unimodal distance functions in geometry
3. Binary Search
10. Convex Hulls
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
3. Divide & Conquer (merge hull)
4. Quickhull (throw-away principle)
6. Chan's Algorithm
7. Kirkpatrick-Seidel's ultimate algorithm (PostScript)
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
11. Visibility (Hidden-Line Problems)
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
12. Updating Triangulations of Points and Line Segments
1. Updating Triangulations:
1. Sergei Sauchenko's Tutorial on inserting and deleting vertices and edges from triangulations (with interactive Java applets)
13. Intersection Problems
1. Intersecting convex polygons:
1. Slab method of Shamos and Hoey
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
14. Proximity Graphs, Voronoi Diagrams and Polyhedral Computations
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
6. Voronoi Diagrams:
7. Applications of 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)
15. Linear Programming
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
16. Facility Location
1. The minimax facility location problem
2. The smallest enclosing circle:
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
17. Mobility of Objects in Space
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
1. A historical introduction to linkages by Joseph Malkevitch
3. Planar Machines' web site. An invitation to Topology. (multiple link linkages! fantastic site!!!)
7. Convexifying Polygons:
18. Degeneracies in Computational Geometry
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):
2. Point-line 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

# 22. Visualization

1. Nice Projections:
2. Aperture-Angle Optimization Problems:
1. The Spindle Torus
2. Kepler's Apples and Lemons 