Untangling Triangulations through Local Explorations

Written with Pankaj Agarwal and Bardia Sadri.

In Proc. 24th Annual Symposium on Computational Geometry, pages 288-297, 2008.

Downloads: PDF, PS

Abstract: 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 the vertices of the mesh and thus potentially turns a mesh invalid, or as we call it, tangled. We introduce the notion of locally removable region, which is a certain tangled area in the mesh that allows 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 the 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.