# Item

ITEM ACTIONSEXPORT

Released

Journal Article

#### Computing Large Planar Regions in Terrains, with an Application to Fracture Surface

##### MPS-Authors

##### Locator

There are no locators available

##### Fulltext (public)

There are no public fulltexts available

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Smid, M., Ray, R., Wendt, U., & Lange, K. (2004). Computing Large Planar Regions
in Terrains, with an Application to Fracture Surface.* Discrete Applied Mathematics,* *139*, 253-264.

Cite as: http://hdl.handle.net/11858/00-001M-0000-000F-295E-1

##### Abstract

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 $\IS^2$, 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(n^2 \log n (\log\log n)^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.