I would probably try an approach with the Graham-Scan Algorithm:
Step 1: From your point quantity, you take the point P1 with minimal y-Coord ( if there are many, choose the one with the minimal x-coord )
Step2: Calculate the Angle from all edges that include P1 to the x-Axis and sort all points by the just calculated angles in a list let's call it L. So you've got a List L = { P1, P2, ..., Pn }
Step3: Pseudocode From i = 3 till n do { if( Pi from P(i-1) is reachable with an inner Angle >= 180° delete P(i-1) from L. Also delete all P(i-k) if Pi is reachable with an inner angle >= 180° }
That should work for your 2D stuff..
*edit yea I should probably mention that the result is the Convex Hull
in L and btw. if there are a couple of points that have the same angle, they'll also be sorted descending by their Distance to P1.
About the performance: The point P1 is found within O(n) Sorting the Angles takes O( n*logn) and each Point is added exactly one time in L and possible deleted one time => O(n) Therefore you have a Runtime of O(n*logn) which is pretty good considering other Algorithms that take O(n^2)