Please use this identifier to cite or link to this item:
Title: Flip-flop: Convex hull construction via star-shaped polyhedron in 3D
Authors: Gao, M.
Cao, T.-T.
Tan, T.-S. 
Huang, Z.
Keywords: Delau-nay triangulation
Incremental insertion
Lawson's flip
Regular triangulation
Issue Date: 21-Mar-2013
Citation: Gao, M.,Cao, T.-T.,Tan, T.-S.,Huang, Z. (2013-03-21). Flip-flop: Convex hull construction via star-shaped polyhedron in 3D. Proceedings of the Symposium on Interactive 3D Graphics : 45-54. ScholarBank@NUS Repository.
Abstract: Flipping is a local and efficient operation to construct the convex hull in an incremental fashion. However, it is known that the traditional flip algorithm is not able to compute the convex hull when applied to a polyhedron in R3. Our novel Flip-Flop algorithm is a variant of the flip algorithm. It overcomes the deficiency of the traditional one to always compute the convex hull of a given star-shaped polyhedron with provable correctness. Applying this to construct convex hull of a point set in R3, we develop ffHull, a flip algorithm that allows nonrestrictive insertion of many vertices before any flipping of edges. This is unlike the well-known incremental fashion of strictly alternating between inserting a single vertex and flipping. The new approach is not only simpler and more efficient for CPU implementation but also maps well to the massively parallel nature of the modern GPU. As shown in our experiments, ffHull running on the CPU is as fast as the best-known convex hull implementation, qHull. As for the GPU, ffHull also outperforms all known prior work. From this, we further obtain the first known solution to computing the 2D regular triangulation on the GPU. © 2013 ACM.
Source Title: Proceedings of the Symposium on Interactive 3D Graphics
ISBN: 9781450319560
DOI: 10.1145/2448196.2448203
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.


checked on Nov 8, 2018

Page view(s)

checked on Nov 9, 2018

Google ScholarTM



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