| Without Deletions | With Deletions |
Most of the major sorting algorithms have corresponding convex hull algorithms in the plane: Quicksort and Mergesort correspond closely to Quickhull and divide-and-conquer. Even selection sort and insertion sort have analogues in gift-wrapping and incremental algorithms. One sorting algorithm that is noticeably absent from this list is Heapsort.
Heaphull is a planar convex hull algorithm whose main data structure is a kinetic heap. We heap the points according to an "up" direction, and mark the topmost point as being on the convex hull. As we rotate the up direction, points move up and down in the heap. Every point that appears at the top of the heap is added to the convex hull. The hull is complete when the first point reappears on the hull.
Unfortunately, the best bound on the running time that we can establish is O(n log2 n), due to the fact that maintaining the event queue takes O(log n) time.
For more details, please see:
This is joint work with Andrea Mantler.