|
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 |
Size | Format |
|---|
| soda.pdf | pre-published version | 211Kb | Adobe PDF | View/Open |
|
All items in this Repository are protected by copyright, with all rights reserved.
|
