Performant algorithm to find edges without cross overs I have a series of graphs with points plotted like this:



Like in the image, I need to join these points to create a complete edge. I am currently doing this with nearest-neighbour, but because I don't know the starting position sometimes this can result in crossed paths.

I could resolve this with more costly algorithms like 2-opt, but because this is being used in real time graphics it isn't quite performant enough.

It might help to know all of these graphs are mapping slightly deformed ovals and so they will have no intrusions. I basically need something that would act as if a rubber band was placed over the points on a graph.

I feel there's probably a better way to do this rather than relying on generic path optimisation algorithms?
As it is mentioned in this paper, you can find a concave-hull of points in a 2-dimensional plate in $O(n \log n)$ (as complex as finding a convex hull).