Convex Hull

From ResearchWiki

Jump to: navigation, search
  • Graham scan (n log n) (use Andrew's modification)
  • Jarvis March (nh)
  • Preparata and Hong (divide and conquer)
  • Kirkpatrick-Seidel ("ultimate convex hull": marriage before conquest)
  • Clarkson/shor: n log h.
  • Chan's combination of Graham Scan/Jarvis March (n log h)
  • Wenger's randomized quickhull
  • Chan/Snoeyink/Yap deterministic quickhull

3D: Chand/Kapur (gift wrapping) Preparata Hong Randomized incremental construction.

Retrieved from "http://www.cs.utah.edu/~suresh/mediawiki/index.php/Convex_Hull"
Personal tools