Computational Geometry Auxiliary Notes

Please find below auxiliary content and notes that are in addition to material that is found in the textbook. Note: some of the links on this page are only accessible through online libraries that are restricted to campus computers. So please view this page from a campus computer or through a campus VPN.

Additional Readings:

• The Jarvis March Convex Hull Method:
  • Gift wrapping convex hull algorithm.
• Chan's Simple Output-Sensitive Convex Hull Algorithm (mostly for cs266 students):
  • Wikipedia description.
  • T.M. Chan, Optimal output-sensitive convex hull algorithms in two and three dimensions, Discrete and Computational Geometry, Springer New York, Volume 16, Number 4 / April, 1996, Pages 361-368.
• Divide-and-conquer convex hulls:
  • Some nice slides by Carola Wenk on the divide-and-conquer approach for convex hulls.
  • Analyzing divide-and-conquer algorithms using The Master Theorem.
• Upper hull binary search. Reading Section 1-3 in the following paper gives the binary search method:
  • Overmars and van Leeuwen, Maintenance of Configurations in the Plane.
• The Four Color Theorem:
  • Discussion from wikipedia.
• Polygon triangulation:
  • Some nice notes by Subhash Suri.
  • Yap, Parallel triangulation of a polygon in two calls to the trapezoidal map. This paper is a parallel version of a simple method for polygon triangulation based on two calls to an algorithm for computing trapezoidal maps.
• Upper/lower Envelopes:
  • Davenport-Schinzel sequences
• 2-Dimensional Linear Programming:
  • Deterministic Linear-time Algorithm
• Range trees:
  • Willard, New Data Structures for Orthogonal Range Queries .
  • Chazelle and Guibas,
    Fractional cascading: I. A data structuring technique
    Fractional cascading: II. Applications
    
• Point location:
  • Sarnak and Tarjan, Planar point location using persistent search trees .
  • Kirkpatrick's planar point location method. See also Dillabaugh's summary and Stiftinger's notes.
• 3D Convex Hulls:
  • Chan's Implementation of 3D Divide-and-Conquer Convex Hulls.
  • Connection between convex hulls and Delaunay triangulations.