Saturday, January 15, 2011

Computational Geometry on the Web

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


General Links - Computational Geometry:

General Links - More Geometry:


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
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:
    1. The plumb-line algorithm
    2. More on the plumb-line algorithm
  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
      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
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
    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)
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:
    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
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
        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
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
      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
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
    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)
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
    1. Geometric Series
    2. Prune-and-Search Algorithm Applet
16. Facility Location
  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
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
  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
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):
    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)

Posted by Unknown at 4:59 AM
Labels:

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)