I'm working with a closed, smooth, planar curve. I don't know the curve exactly, but I do have an effectively-random collection of points along the curve. What's a good way to estimate the curve length from that information?
I can think of two methods:
EDIT: The curve I'm working with is the solution of f(x,y)=0, and I now see that -- in my case -- solutions to this are not necessarily connected. (I.e. it looks like the solutions are multiple, disjoint curves -- whether these are one curve or many is a matter of semantics.) That rules out method 1.
1) Start at some point. Find the distance to the closest point. From that point, find the distance to the next closest point. Rinse, lather, repeat and sum up the distances.
2) If there are enough points, make a grid and mark all grid cells that have at least one point in them. The curve must pass through each of those cells, so the curve length can be estimated from the number of marked cells. (I guess, more specifically, this would be using the Cauchy-Crofton formula as described by Do Carmo on p 45-46 in his classic Differential Geometry book.) However, this method may run into trouble if there aren't points in every cell that the curve passes through.
The first method seems inefficient (have to repeatedly search through all the unused points) but accurate. The second would be faster, but less accurate.
Thoughts on those methods or other methods?
I'd recommend the first method. As you observed, it has unpleasant $O(n^2)$ behavior. If you care about efficiency, you need to do something to fix this. The standard way would be to use sorting, or some sort of spatial index, to reduce the number of comparisons you have to do. For example, set up a grid, as in your second algorithm. Make a pass through the list of points, finding out which cell each one falls in. For each cell, keep a list of the points it contains. Then, when looking for closest neighbors, you only have to look in the current point's cell and nearby ones. Some fine-tuning is required to decide how fine/coarse the grid should be.