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.

Computational geometry, Optimization, Planar region, Terrain
Discrete Applied Mathematics
Carleton University

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