20040430
Computing large planar regions in terrains, with an application to fracture surfaces
Publication
Publication
Discrete Applied Mathematics , Volume 139  Issue 13 p. 253 264
We consider the problem of computing the largest region in a terrain that is approximately contained in some twodimensional plane. We reduce this problem to the following one. Given an embedding of a degree3 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 threedimensional (topographical) images of fracture surfaces of metals obtained by confocal laser scanning microscopy.
Additional Metadata  

Computational geometry, Optimization, Planar region, Terrain  
dx.doi.org/10.1016/j.dam.2002.11.004  
Discrete Applied Mathematics  
Organisation  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
