Best Algorithm to find the edges (polygon) of vertices

Question

I have a large array of vertices, some of them are edges, some are redundant (inside the shape) and I want to remove those.

The simplest algorithm I could think of is checking one by one if they hit the shape formed by the others. But it should be a very slow algorithm.

I thought about picking one from the edge (the one farthest from origin per example) and calculate the longest path from this start... should get the edge path, right?

Any suggestion?

Answer 1

The trick with polyhedral algorithms is choosing one that fits with your input and your desired output, since there is more than one way to represent a polyhedron and converting between the representations can be expensive. In this case, you are starting with points and want to end with vertices, so the Graham scan algorithm to compute the vertices of the convex hull should do the trick, though it might take some effort to extend it past the 2-D case. It's O(n log n) in the number of input vertices.