Re:Finding a minimum polygon of a set of points
by laex on Monday April 06, 2015 @07:07PM
(#9331209)
Some time back, I wrote a simple convex hull computing code in Go. If anyone's interested: https://github.com/hemantasapkota/go-convexhull
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