Finding Planar Regions in a Terrain - In Practice and with a Guarantee

Stefan Funke, Theocharis Malamatos, Rahul Ray

We consider the problem of computing large connected regions in a triangulated terrain of size $n$ for which the normals of the triangles deviate by at most some small fixed angle. In previous work an exact near-quadratic algorithm was presented, but only a heuristic implementation with no guarantee was practicable. We present a new approximation algorithm for the problem which runs in $O(n/\epsilon^2)$ time and---apart from giving a guarantee on the quality of the produced solution---has been implemented and shows good performance on real data sets representing fracture surfaces consisting of around half a million triangles. Further we present a simple approximation algorithm for a related problem: given a set of $n$ points in the plane, determine the placement of the unit disc which contains most points. This algorithm runs in linear time as well.

Proc. 20th ACM Symposium on Computational Geometry (SoCG) 2004, New York

a very preliminary version also appeared in Proc. 20th European Workshop on Computational Geometry (EWCG) 2004, Sevilla