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.
a very preliminary version also appeared in
Proc. 20th European Workshop on Computational Geometry (EWCG) 2004, Sevilla
PDF