CS 373 Combinatorial Algorithms Geometric Triangulation

Alper Üngör

May 9, 1997

• Contents
• Introduction
• Algorithms
  • Plane Sweep Algorithm for Triangulation and Convex Hull
  • Edge Flip Algorithm for Delaunay Triangulation
• Data Structures
  • Circular Doubly Linked List
  • Quad Edge Data Structure
• Implementation
  • Non-Degenarcy Assumption
  • Java and Animation
• Analysis
  • Analysis of Plane Sweep Algorithm
  • Analysis of Edge Flip Algorithm
  • Space Requirement
• Conclusion
• References
• Appendix : Java Code of the Geometric Triangulation Program
• About this document ...