Please use this identifier to cite or link to this item:
Title: Flip to Regular Triangulation and Convex Hull
Authors: Gao, M 
Cao, TT 
Tan, TS 
Issue Date: 1-Feb-2017
Publisher: Institute of Electrical and Electronics Engineers (IEEE)
Citation: Gao, M, Cao, TT, Tan, TS (2017-02-01). Flip to Regular Triangulation and Convex Hull. IEEE Transactions on Visualization and Computer Graphics 23 (2) : 1056-1069. ScholarBank@NUS Repository.
Abstract: Flip is a simple and local operation to transform one triangulation to another. It makes changes only to some neighboring simplices, without considering any attribute or configuration global in nature to the triangulation. Thanks to this characteristic, several flips can be independently applied to different small, non-overlapping regions of one triangulation. Such operation is favored when designing algorithms for data-parallel, massively multithreaded hardware, such as the GPU. However, most existing flip algorithms are designed to be executed sequentially, and usually need some restrictions on the execution order of flips, making them hard to be adapted to parallel computation. In this paper, we present an in depth study of flip algorithms in low dimensions, with the emphasis on the flexibility of their execution order. In particular, we propose a series of provably correct flip algorithms for regular triangulation and convex hull in 2D and 3D, with implementations for both CPUs and GPUs. Our experiment shows that our GPU implementation for constructing these structures from a given point set achieves up to two orders of magnitude of speedup over other popular single-threaded CPU implementation of existing algorithms.
Source Title: IEEE Transactions on Visualization and Computer Graphics
ISSN: 1077-2626
DOI: 10.1109/TVCG.2016.2525724
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
File Description SizeFormatAccess SettingsVersion 
Flip_to_Regular_Triangulation_and_Convex_Hull.pdfAccepted version1.98 MBAdobe PDF



Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.