Saturday, January 15, 2011

The C# Tutorial

Posted by Unknown at 5:54 AM 0 comments

Relevant Algorithm Animations/Visualizations (in Java)


This collection of links to animations/visualizations of algorithms:
  • is based on the textbook "Algorithms in C++" by Robert Sedgewick, Addison Wesley and Benjamin Cummings (nå: Pearson), 1992.
  • do only cover those parts of the textbook relevant to the curriculum for the students at HiG.
  • tries to cover a lot of different concepts within the area of "Computer Algorithms".
  • do not claim to be complete in any sense, they are selected from the best ones the lecturer knows so far.
  • are immediately runable (without any further installation of software packages) inside your browser (provided the use of a Java enabled browser)

Thanks to everyone that made these good/excellent animations available  ! ! !
(I hope they will be maintained, for the pleasure of the rest of us ....) Do You know about any interesting, relevant, or good animations ? Please, let me know .....
 

 

Collections (pages with a LOT of good animations):

  1. Algoritmik: Animering af algoritmer
  2. Animal Animations Collection
  3. Computer Science Tutorial Page
  4. Web Data Structures and Algorithms
  5. TRAKLA2 - Exercises   (NOTE: Remove one of the "/exercises" in all the pages linked to!)
  6. Sorting Algorithm Animations   (All sorting methods in the curriculum. See/use the options at the first line!)
  7. The Sort Algorithm Animator V1.0   (All sorting methods in the curriculum)
  8. Vivo Animations   (requires Vivio ActiveX Player installed!)
  9. hatful of hollow - Visualising Sorting Algorithms   (a different approach .....)


 

Chapter 3: Elementary Data Structures

    Link/URL:   Keywords:   Page:   Comments:
  1   Java Applets Centre: Linked List     17-22  
  2   Linked List     17-22  
  3   Java Applets Centre: Stack     25-26  
  4   Stack     25-26  
  5   Stack Operation Demonstration Program     27   Reads and calculates a postfix-expression.
  5B   TRAKLA2 - Postfix evaluation     27   Calculates Postfix-expression (both demo ("Model answer") and self-test).
  6   Infix, Postfix, Prefix Parser   URL not found!   28   See the program code in the textbook.
  7   Java Applets Centre: Queue     30-31  
  8   Java Applets Centre: Cyclic Queue     30-31  
  9   Circular Queue     30-31  
  10   Train Sorting with Stacks       Practical "fun" use of stacks.

 

Chapter 4: Trees

    Link/URL:   Keywords:   Page:   Comments:
  1   An Expression Tree Builder and Evaluator     40-43  
  2   Expression Tree Demonstration Program     40-43  
  3   Postfix Enumeration Demonstration Program     42  
  4   Java Applets Centre: Binary Tree Traversal     44-49  
  5   Interactive Data Structure Visualizations     44-49   Choose "Trees - Traversals" in the upper left corner.
  6   Binary Treesome - The Applet     44-49   Choose "Tree: Standard" and "Insert", Build Tree,
  Choose "Iteration", Practice!

 

Chapter 5: Recursion

    Link/URL:   Keywords:   Page:   Comments:
    Textbook Relevant:
  1   The Fibonacci Numbers and the Golden section       A lot of fun stuff about Fibonacci-numbers.
  2   Fibonacci Interactive       Shows the recursive "call tree". Use the "arrows" in the upper left corner.
    Theory Basics:
  1   Introduksjon til rekursjon       Source: http://www.ifi.uib.no/undervisning/iv132/forel/f02.ppt
  2   Lecture3; Linked Lists; Recursion       Go to "Recursion" - 40% from the bottom of the page.
  3   Lecture 3 - Recursion      
  4   Tom Kelliher's Lectures:
                * Introduction to Recursion
                * Recursion, Concepts and Examples
                * More Recursion
                * Recursion, Searching, and Efficiency
                * Recursion as a Problem Solving Technique 		     
    Specific:
  1   The Animation of Recursion       Money Collector, Factorial, String Reversal, Quicksort, see exercise 6 and 9.
  2   Dynamic Programming: Towers of Hanoi       See exercise 6.
  3   Towers of Hanoi       See exercise 6.
  4   Tower of Hanoi History & Instructions       See exercise 6.
  5   The Tower of Hanoi       See exercise 6.
  6   Towers from Hanoi       See exercise 6.
  7   Java Applets Centre: Tower of Hanoi       See exercise 6.
  8   Java Applets Centre: N-Queens Problem       See exercise 9.
  9   The Eight Queens Problem       See exercise 9.
  10   "The Eight Queens Problem"       See exercise 9.
  11   Backtracking: The Queens Problem       See exercise 9.
  12   Generate Solutions to n-Queens Problem       See exercise 9.
  13   Rat In a Maze       See Exam of 12.12.1995 number 4.
  14   MazeWorks - MazeGen       See Exam of 12.12.1995 number 4.
  15   Church's Thesis       Some mathematical.
  16   Recursion and Graphics       Pictures and program code (in Lisp).
  17   Chris Hruska's Stupid Recursion Tricks       Entertainment .....
    Permutation:
  1   Information on Permutations      
  2   Generate Permutations      
  3   Permutations       Follow links in the text, and at the end of the document.
    Fun:
  1   Recursive Painting      

 

Chapter 8: Elementary Sorting Methods

    Link/URL:   Keywords:   Page:   Comments:
  1   Animation of Sorting Algorithms   Selection   URL not found!   Tickmark "Selection".
  2   Visual Sorting   Selection, Insertion, Bubble   URL not found!   Choose method in the middle at the bottom.
  3   The xSortLab Applet   Selection, Insertion, Bubble     Choose "Selection", "Insertion" or "Bubble".
  4   Sorting Algorithms   Selection, Insertion, Bubble, Shell     Choose Sorting method at the bottom left of the first window.
  5   Sorting Algorithms in C++   Selection, Insertion, Bubble, Shell     Choose Sorting method at the top and which array to be sorted.
  6   Animation of Sorting Algorithms   Selection, Insertion, Bubble, Shell   101-102 and 111   Covers all seven sorting methods in the textbook,
  but choose here one of the four relevant methods.
  (alternatively use: dmh2000 - Sorting Dynamics (Bubble and Shell))
  7   Animation of Sort Algorithms   Selection, Insertion, Bubble, Shell     Press the button at the top of the page.
  Choose sorting method under "Algorithms" at the top.
  8   The Animator   Selection, Insertion, Bubble, Shell     Choose method in the lower right corner.
  8B   Sorting Out Sorting (ver 2.0 - Demo)   (Linear) Insertion, Bubble, Shell     Choose method(s) at upper left, click "Add" and "Run Playlist".
  9   Java Applets Centre: Selection Sort   Selection    
  10   Example of Sorting Algorithm's Animation   Selection    
  11   Java Applets Centre: Insertion Sort   Insertion    
  12   Data Structures and Algorithms: Sorting   Insertion     Press the "Run the Animation"-button in the middle of the page.
  13   Example of Sorting Algorithm's Animation   Insertion    
  14   Java Applets Centre: Bubble Sort   Bubble    
  15   Bubble   Bubble    
  16   Example of Sorting Algorithm's Animation   Bubble    
  17   Bubble Sort   Bubble    
  18   Bubblesort-Animation   Bubble     "Fun".
  19   Bubble Sort Program   Bubble     Note: Increasing sorting, and not decreasing
  (as in the textbook).
  20   Shell Sort   Shell    
  21   Shell Sort Animation   Shell    
  22   Java Animations of Shellsort and variants   Shell     Choose "Increment Sequence" at the bottom right.
  23   AIA: Shellsort   Shell     guest / gjovik     Choose "Shellsort".
  24   AIA: Distribution Counting   Distribution Counting     guest / gjovik     Choose "Distribution Counting".
  Note: Last for-loop is increasing, and not decreasing
  (as in the textbook).
  25   YouTube: What different sorting algorithms sound like.   Insert, Bubble, Selection, Merge, Gnome     Fun.

 

Chapter 9: Quicksort

    Link/URL:   Keywords:   Page:   Comments:
  1   AIA: Quicksort      
  2   The xSortLab Applet       Choose "Quicksort".
  NOTE: Uses the left one as partition element.
  3   Sorting Algorithms in C++       Choose "Quicksort" at the top and which array to be sorted.
  4   The Animation of Recursion - Quicksort       NOTE: Uses the left one as partition element.
  5   Sorting Algorithms       Choose "Quicksort" at the bottom left of the first window.
  6   Visual Sorting   URL not found!     Choose "Quicksort" in the middle at the bottom.
  NOTE: Uses the middle one as partition element and moves it to the front.
  7   Animation of Sorting Algorithms   URL not found!     Tickmark "Quicksort".
  8   Sorting - Quicksort   ???     Choose "Quicksort" in the window at the bottom.
  9   The Animator       Choose "Quicksort" in the lower right corner.
  9B   Sorting Out Sorting (ver 2.0 - Demo)       Choose "Quicksort" at upper left, click "Add" and "Run Playlist".
  NOTE: Uses the left one as partition element.
  10   Quicksort      
  11   Java Applets Centre: Quick Sort      
  12   Quicksort-Animation       "Fun".
  13   Animation of Sorting Algorithms     125   Covers all seven methods in the textbook, but choose here "Quicksort".
  (alternatively use: dmh2000 - Sorting Dynamics)

 

Chapter 11: Priority Queues / Heaps

    Link/URL:   Keywords:   Page:   Comments:
  1   Interactive Data Structure Visualizations     148-154   Choose "Trees - Priority Queue" in the upper left corner.
  2   Heaps     148-154   Press the button "Run The Animation" at the bottom.
  2b   Java Applets Centre: Priority Queue     148-154   Note:Smallest number as the root/at the top!
  3   A Priority Queue Tester   URL not found!     Build your own Heap 1
  4   Animation of Sorting Algorithms   URL not found!   156-159   Tickmark "Heapsort".
  5   Data Structures and Algorithms: Heap Sort     156-159   Press the button "Run Heap Sort" at the bottom.
  6   AIA: Heapsort     156-159  
  7   Interactive Data Structure Visualizations     156-159   Choose "Sorting - Heap Sort" in the upper left corner.
  8   Sorting Algorithms     156-159   Choose "Heapsort" at the bottom left of the first window.
  9   Sorting Algorithms in C++     156-159   Choose "Heapsort" at the top and which array to be sorted.
  9B   Sorting Out Sorting (ver 2.0 - Demo)     156-159   Choose "Heapsort" at upper left, click "Add" and "Run Playlist".
  10   Heapsort     156-159   Press the button "ANIMATION" at the bottom.
  11   Heap sort visualization: Java applet     156-159   Note: Downheaps already when inserting (backwards)!
  12   Animation of Sorting Algorithms     158-159   Covers all seven methods in the textbook, but choose here "Heapsort".
  (alternatively use: dmh2000 - Sorting Dynamics)
  13   YouTube: Heapsort audibilization.       Fun.

 

Chapter 12: Mergesort

    Link/URL:   Keywords:   Page:   Comments:
  1   Merge Example (of two arrays)     164  
  2   MergeSort demo with comparison bounds     165-166   See in the middle of the page/document.
  3   Java Applets Centre: Merge Sort     165-166  
  4   Mergesort     165-166  
  5   Sorting - Mergesort   ???   165-166   Choose "Mergesort" in the window at the bottom.
  6   The Animator       Choose "Mergesort" in the lower right corner.
  7   The xSortLab Applet       Choose "Mergesort". Note: Operates a little different from the textbook !
  8   Sorting Algorithms in C++     165-166   Choose "Mergesort" at the top and which array to be sorted.
  9   Animation of Sorting Algorithms     172-174   Covers all seven methods in the textbook, but choose here "Mergesort".
  (alternatively use: dmh2000 - Sorting Dynamics)

 

Chapter 14: Elementary Searching Methods

    Link/URL:   Keywords:   Page:   Comments:
  1   Java Applets Centre: Linear Search     195   Unsorted array.
  2   Java Applets Centre: Binary Search     198-201   Sorted array.
  3   Java Applets Centre: Binary Search Tree (Search)     203-205  
  4   Java Applets Centre: Binary Search Tree (Insert, Delete)     205-211  
  5   Binary Treesome - The Applet     203-211   Choose "Tree: Sorted" and "Insert", Practice Adding/Deleting/Searching Nodes!
  6   Animated Binary Tree     203-211   Build your own Binary Tree 1
  7   Binary Search Trees   URL not found!   203-211  
  8   Interactive Data Structure Visualizations     203-211   Choose "Trees - Search Trees" in the upper left corner.
  9   Binary Search Tree Program     203-209  
  10   Binary Search Tree   ???   203-209  
  11   Standard Binary Search Tree     203-209  

 

Chapter 15: Balanced Trees

    Link/URL:   Keywords:   Page:   Comments:
  1   Top-Down 2-3-4 Trees / Red-Black Trees   URL not found!   215-229   Note: Maximaze the windows for the animation !
  1B   Graphical 2-3-4 Tree     215-219  
  2   AIA: 234 Tree     215-229  
  3   Red/Black Tree Demonstration     220-229  
  4   Data Structures and Algorithms: Red-Black Trees     220-229   Press the "Run Red-Black Tree Animation"-button at the bottom.
  5   Topic #18: Red-Black Trees     220-229  
  6   Red-Black Trees     220-229  
  7   AIA: Red Black Tree     220-229   guest / gjovik     Choose "Red Black Tree".
  8   Binary Search Tree (AVL)     220-229   Open "Options" in upper left corner - choose from menu.
  9   Binary Search Trees (Stromceky)     220-229   Choose "Red-black tree" from upper menu.
  10   Red-Black Tree Animation     220-229   Shows split and rotation in a good way.
  11   dmh2000 Red-Black Trees     220-229
  12   Red-Black Binary Search Tree   ???   220-229  
  13   Rotation Tutorial   URL not found!     Only about rotation of trees.

 

Chapter 16: Hashing

    Link/URL:   Keywords:   Page:   Comments:
  1   Separate-Chaining Hash Table   Separate Chaining   234-236  
  2   Hash Table Demonstration - Separate Chaining   Separate Chaining   234-236  
  3   Linear-Probe Hash Table   Linear Probing   236-239  
  4   Data Structures and Algorithms: Hash Tables   Linear Probing   236-239   Press the "Run the Animation"-button at the bottom.
  5   Hash Table Demonstration - Linear Probing   Linear Probing   236-239  
  6   Double/Quad Hash Table   Double/Quad Hashing   239-242  
  7   Hashing Animation Tool   Several .....    

 

Chapter 22: File Compression

    Link/URL:   Keywords:   Page:   Comments:
  1   Huffman Compression Applet   URL not found!   324-330   Write in your own text to compress!
  2   Huffman Encoding     324-330   Press the button "Run The Animation" at the bottom.
  3   Huffman Coding     324-330   Shockwave demo.
  4   Practical Huffman Coding     324-330  
  5   Adaptive Huffman Compression     324-330  
  6   Lossless Data Compression (Huffman / Lempel-Ziv)     (324-330)   Animation of Lempel-Ziv in the middle of the page.
  7   LZW     (324-330)   Press the button almost at the bottom of the page.
    Compression Resources:
  1   Mitsuharu ARIMURA's Bookmarks on Source Coding/Data Compression      Huge list of compression resources.
  2   Compression Pointers   URL not found!    
  3   DataCompression.info   ???     See escpescially the "Huffman Coding" and its
  "Tutorials, Reference, Presentations"-section at the bottom.
    Lectures:
  1   Introduction to data compression       This article is curriculum in our course!
  2   Michael Dipperstein's Page O'Stuff       See comprehensive Compression-links in the upper left corner.
  3   Compression Algorithms       A lot of good theory material.
  4   Huffman Coding       "Long" detailed explanation!
  5   LZW Data Compression       "Long" detailed explanation with commentary!
    FAQs:
  1   Compression FAQ (HTML)       Official FAQ.   ASCII-/TXT-version
  2   PKWARE: FAQs (on PKZip)       FAQs about PKZIP for different platforms/OS.

 

Chapter 29-33: General (Terms) About Graphs

    Link/URL:   Keywords:   Page:   Comments:
  1   Graph Theory Tutorial - Glossary of Terms      
  2   Graph Theory Tutorial - Graph Terminology       Two pages. Se also two "Here"-links at the second page.
  3   JGraphEd       Excellent General Tool for Graph-drawing/-testing.   Download here.
  4   Java-Graph-Editor   URL not found!     Very comprehensive. Press the button "Show Java-Graph-Editor".
  5   Programs for Graph Algorithm Package (IAPPGA)       Plain, Weighted and/or Directed graphs. Excellent page!
  6   Games on Graphs      
  7   Mathmania Graph Theory   URL not found!    

 

Chapter 29: Elementary Graphs Algorithms

    Link/URL:   Keywords:   Page:   Comments:
  1   Class notes CS251B - Winter 1997: Graphs     415-423   See especially the animation near the bottom.
  2   Interactive Data Structure Visualizations - Categorizing
  (Connected?, Cycles?, Tree?) 		    417   Choose "Graphs - Categorizing" in the upper left corner.
  3   Interactive Data Structure Visualizations - Representation
  (Adjacent Matrix) 		    418-421   Choose "Graphs - Representation" in the upper left corner.
  4   Graph Theory Tutorial - Graph Representation
  (Adjacent Matrix, Adjacent List, Trees) 		    418-423   Three pages.
  See especially the last "Here"-link at the first page.
  5   Interactive Data Structure Visualizations - Searches (DFS/BFS)     423-433   Choose "Graphs - Searches" in the upper left corner.
  6   BFS and DFS   Search Forest   423-433  
  7   Java Applets Centre: Graph Traversal (DFS/BFS)     423-433  
  8   Class notes CS251B - Winter 1997: DFS     423-428   See especially the animation at the bottom.
  9   Example of Graph Algorithm's Animation - Depth-First-Search     423-428  
  10   Graph Algorithms Animation - DFS     423-428   Choose "Depth-First-Search" from "Select Menu".
  11   Class notes CS251B - Winter 1997: BFS     431-433   See especially the animation at the bottom.
  12   Example of Graph Algorithm's Animation - Breadth-First-Search     431-433  
  13   Graph Algorithms Animation - BFS     431-433   Choose "Breadth-First-Search" from "Select Menu".
  14   Wire Routing (Using Queues) - BFS       Practical "fun" use of BFS/Queue.
  15   BFS/DFS Animations     433   Shows the difference in a clear way.

 

Chapter 30: Connectivity

    Link/URL:   Keywords:   Page:   Comments:
  1   Tutorial on Connected Components     437-438  
  2   Sets Union/Find Demonstration Program     441-449   The demo shows Union with Path Compression (without Weight Balancing)
  over the edges: 01, 43, 23, 56, 14, search(3), 89, 86, 37,
  search(5), search(6), 75, search(6).
  3   Graphical Union-Find Structure     441-449   Build yourself Union(-Find) (without Path Compression and Weight Balancing).
  4   Union/Find Algorithm Visualization     441-449   Union with Path Compression.

 

Chapter 31: Weighted Graphs

    Link/URL:   Keywords:   Page:   Comments:
    NOTE:The code at page 455 in the textbook is another
  implementation (it uses adjacency list and indirect heap) of Prim's (MST)
  and Dijkstra's (SP) algorithm at page 466 (that uses adjacency matrix and
  an unsorted/unordered array).
  (Kruskal's code at page 460 uses a different/another algorithm for MST.) 		     
  1   Class notes CS251B - Winter 1997: Minimum Spanning Tree     452-458   See especially the animation at the bottom.
  2   Graph Theory Tutorial - Minimum Spanning Tree   URL not found!   452-458  
  3   Minimum Spanning Tree Demonstration Program     452-458  
  4   Graph Algorithms Animation - Minimum Spanning Tree     452-458   Choose "Minimum Spanning Tree" from "Select Menu".
  Increase the delay also.
  5   Prim/Kruskal/Dijkstra's Algorithm     454-467   Choose "Prim", "Kruskal" og "Dijkstra" Algorithm.
  6   5.7.1 Dijkstra Algorithm     461-465  
  7   Data Structures and Algorithms: Dijkstra's Algorithm     461-465   Press the button "Run the Animation" at the bottom.
  8   Shortest Path Problem: Dijkstra's Algorithm     461-465   Follow the link "Java Applet Demos" along the left margin.
  9   Dynamic Programming: The Shortest Path Module     461-465  
  10   Dynamic Programming: Dijkstra's Algorithm Module     461-465  
  11   Dijkstra's Shortest Path Algorithm Animation in Java   URL not found!   461-465   Build your own graph and test!
  12   Shortest Path Algorithm     461-465  
  13   Class notes CS251B - Winter 1997: Shortest Path     (461-465)  
  14   Graph Algorithms Animation - Shortest Path     461-465   Choose "Shortest Path" from "Select Menu".
  15   Dijkstra's Shortest Path Algorithm     461-465   Build your own graph and test!

 

Chapter 32: Directed Graphs

    Link/URL:   Keywords:   Page:   Comments:
  1   Depth First Search     472-473  
  2   Breadth First Search      
  2B   Application programs - Transitive Closure (Warshall's Algorithm)     473-476   See the second half of the page, and the animation at the bottom.
  3   All Pairs Minimum Routes Problem (Floyd's Algorithm)     476-478  
  4   All Pair Shortest Paths (Floyd's Algorithm)     476-478  
  5   Floyd-Warshall All-Pairs-Shortest-Path Algorithm     476-478  
  5B   Applet Floyd-Warshall     476-478  
  6   Class notes CS251B - Winter 1997: Directed Acyclic Graphs (Dag)     479-481   See especially the animation at the bottom.

 

Chapter 33: Network Flow

    Link/URL:   Keywords:   Page:   Comments:
  1   Graph Theory Tutorial - Flow Problems   URL not found!    
  2   Max Flow min cut Example   URL not found!   487-489  
  3   Max-Flow Problem: Ford-Fulkerson Algorithm     487-489   Follow the link "Java Applet Demos" along the left margin.
  4   Max Flow Applet Home     487-489  
  5   Maximum Flow Algorithm Applet   URL not found!   487-489  
  6   Network Flow       Build yourself !
  7   Max Flow (of Ford-Fulkerson Method)     487-489   Build yourself !
  8   Maximum Flow Algorithms Applet     487-489   Build yourself !

 

Finite State Machine (NOT in the textbook):

    Link/URL:   Keywords:   Comments:
  1   DynaLab Finite State Automation Applet   ?????   Code: See number 2 below.
  2   FSM Animator   ?????   Press the red "Show Program Animator"-button at the bottom.
  Figure: See number 1 above.
  3   The Finite State Machine Explorer   URL not found!   Build your own FSM.   See in the middle of the page.
  4   State Machine Simulator     Build your own FSM.
  5   Finite State Machine   URL not found!   Build your own FSM.
  6   Finite State Machine Drawing   URL not found!  
  7   Finite-State Machine Simulator    
  8   reAnimator: Regular Expression FSA Visualizer     Click pink text, or write your own expression (by clicking "edit" in upper left corner).
  Write input text inside pink field along upper margin.
    Theory:
  1   Wikipedia: FSM    
  2   FSM (by Dr.Matt Stallmann)    
  3   Contemporary Logic Design     See chapter 8-10.
  4   Google Search: lang:"C++" FSM    

 
Posted by Unknown at 5:27 AM 0 comments
Labels: , ,

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 0 comments
Labels:
Subscribe to: Posts (Atom)