New answers tagged

2

Just a quick heuristic idea: Step 1) I would start with determining the convex hull of the original set of points in $\mathcal O(n \log n)$ with the Graham scan. There are various implementations out there (in many languages). Robert Sedgewick has one in its book Algorithms (1983). The Java Version can be found here. Step 2) Then I would remove the points ...


3

I posted a heuristic, based on a Delaunay triangulation, on my blog. Basically, you start with the triangulation, including the boundary of the convex hull. You then roam the boundary, looking for segments belonging to a triangle whose third vertex is not yet on the boundary. When you find one, you remove the segment and replace it with the other two sides ...


Top 50 recent answers are included