HKUST Library Institutional Repository Banner

HKUST Institutional Repository >
Computer Science and Engineering >
CSE Conference Papers >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1783.1/3278
Title: Maintaining deforming surface meshes
Authors: Cheng, Siu-Wing
Dey, Tamal K.
Keywords: Deforming surface
Surface mesh
Approximation
Issue Date: 2008
Citation: Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms, San Francisco, California, USA, 20-22 January 2008, p. 112-121
Abstract: We present a method to maintain a mesh approximating a deforming surface, which is specified by a dense set of sample points. We identify a reasonable motion model for which a provably good surface mesh can be maintained. Our algorithm determines the appropriate times at which the mesh is updated to maintain a good approximation. The updates use simple primitives, and no costly computation such as line-surface intersection is necessary. Point insertions and deletions are allowed at the updates. Each update takes time linear in the size of the current sample set plus the new sample points inserted. We also construct examples for which, under the same model, no other algorithm makes asymptotically fewer changes to the mesh than our algorithm.
Rights: © ACM, 2008. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms, p. 112-121.
URI: http://hdl.handle.net/1783.1/3278
Appears in Collections:CSE Conference Papers

Files in This Item:

File Description SizeFormat
soda.pdfpre-published version211KbAdobe PDFView/Open

All items in this Repository are protected by copyright, with all rights reserved.