de.mpg.escidoc.pubman.appbase.FacesBean
English
 
Help Guide Disclaimer Contact us Login
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Journal Article

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

MPS-Authors
http://pubman.mpdl.mpg.de/cone/persons/resource/persons45509

Smid,  Michiel
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons45268

Ray,  Rahul
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

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.