# Item

ITEM ACTIONSEXPORT

Released

Conference Paper

#### Computing Large Planar Regions in Terrains

##### External Resource

No external resources are shared

##### Fulltext (restricted access)

There are currently no full texts shared for your IP range.

##### Fulltext (public)

There are no public fulltexts stored in PuRe

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Ray, R., Smid, M., Lange, K., & Wendt, U. (2002). Computing Large Planar Regions
in Terrains. In *IWCIA 2001, 8th International Workshop on Combinatorial Image Analysis (IWCIA-01)*
(pp. 139-152). Amsterdam, the Netherlands: Elsevier.

Cite as: https://hdl.handle.net/11858/00-001M-0000-000F-2F45-D

##### 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 S2, whose vertices are
weighted, compute a connected subgraph of maximum weight that is contained in
some spherical disk of a fixed
radius. We given an algorithm that solves this problem in O(n2 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 a web-based implementation
of this heuristic, and show some results
for terrains representing three-dimensional (topographical) images of
fracture surfaces of metals obtained by confocal laser scanning microscopy.