We consider the problem of computing the largest region in a terrain that is approximately contained in some two-dimensional plane. We reduce this problem to the following one. Given an embedding of a degree-3 graph G on the unit sphere S2, whose vertices are weighted, compute a connected subgraph of maximum weight that is contained in some spherical disk of a fixed radius. We give an algorithm that solves this problem in O(n2logn(loglogn) 3) time, where n denotes the number of vertices of G or, alternatively, the number of faces of the terrain. We also give a heuristic that can be used to compute sufficiently large regions in a terrain that are approximately planar. We discuss an implementation of this heuristic, and show some experimental results for terrains representing three-dimensional (topographical) images of fracture surfaces of metals obtained by confocal laser scanning microscopy.

Additional Metadata
Keywords Computational geometry, Optimization, Planar region, Terrain
Persistent URL dx.doi.org/10.1016/j.dam.2002.11.004
Journal Discrete Applied Mathematics
Citation
Smid, M, Ray, R. (Rahul), Wendt, U. (Ulrich), & Lange, K. (Katharina). (2004). Computing large planar regions in terrains, with an application to fracture surfaces. In Discrete Applied Mathematics (Vol. 139, pp. 253–264). doi:10.1016/j.dam.2002.11.004