Point Location

From ResearchWiki

Jump to: navigation, search
  • Dobkin-Lipton (using slabs): O(logn) query time, O(n2) space.
  • Lipton-Tarjan (using planar separators): linear space.
  • Kirkpatrick hierarchies: linear space, log n time, more practical
  • Edelsbrunner, Guibas, Stolfi: separator-based
  • Sarnak/Tarjan (using persistence)
  • Mulmuley/Seidel: randomized (also see Triangulation)
  • Adamy-Seidel: smallest constant in front of query time.
Retrieved from "http://www.cs.utah.edu/~suresh/mediawiki/index.php/Point_Location"
Personal tools