Department of Mathematics
 Search | Help | Login | pdf version | printable version

Math @ Duke



Publications [#235507] of Pankaj K. Agarwal

Papers Published

  1. Agarwal, PK; Sadri, B; Yu, H, Untangling triangulations through local explorations, Proceedings of the Annual Symposium on Computational Geometry (2008), pp. 288-297 [doi]
    (last updated on 2018/10/21)

    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.
ph: 919.660.2800
fax: 919.660.2821

Mathematics Department
Duke University, Box 90320
Durham, NC 27708-0320