FYI, the algorithm you were describing was to compute a convex hull. It can be done in O(n lg n) time by sorting the points by angle w.r.t. some starting point and then "gift wrapping".

You can find where to add a new point in O(lg h) time with a binary search, but you may need to eject O(h) old points. Points can only be ejected once, so there might still be some nice aggregate bound in terms of n.

http://en.wikipedia.org/wiki/Convex_hull_algorithms