Untangling triangulations through local explorations


Journal Article

The problem of maintaining a valid mesh (triangulation) within a certain domain that deforms over time arises in many applications. During a period for which the underlying mesh topology remains unchanged, the deformation moves vertices of the mesh and thus potentially turns a mesh invalid, or as we call it, tangled. We introduce the notion of locally removable regions, which are certain tangled regions in the mesh that allow for local removal and re-meshing. We present an algorithm that is able to quickly compute, through local explorations, a minimum locally removable region containing a "seed" tangled region in an invalid mesh. By re-meshing within this area, the "seed" tangled region can then be removed from the mesh without introducing any new tangled region. The algorithm is output-sensitive in the sense that it never explores outside the output region. Copyright 2008 ACM.

Full Text

Duke Authors

Cited Authors

  • Agarwal, PK; Sadri, B; Yu, H

Published Date

  • December 12, 2008

Published In

  • Proceedings of the Annual Symposium on Computational Geometry

Start / End Page

  • 288 - 297

Digital Object Identifier (DOI)

  • 10.1145/1377676.1377726

Citation Source

  • Scopus