Please use this identifier to cite or link to this item: https://doi.org/10.1109/TVCG.2016.2525724
DC FieldValue
dc.titleFlip to Regular Triangulation and Convex Hull
dc.contributor.authorGao, M
dc.contributor.authorCao, TT
dc.contributor.authorTan, TS
dc.date.accessioned2022-05-10T09:28:09Z
dc.date.available2022-05-10T09:28:09Z
dc.date.issued2017-02-01
dc.identifier.citationGao, 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. https://doi.org/10.1109/TVCG.2016.2525724
dc.identifier.issn1077-2626
dc.identifier.issn1941-0506
dc.identifier.urihttps://scholarbank.nus.edu.sg/handle/10635/225178
dc.description.abstractFlip 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.
dc.publisherInstitute of Electrical and Electronics Engineers (IEEE)
dc.sourceElements
dc.typeArticle
dc.date.updated2022-05-10T07:27:52Z
dc.contributor.departmentDEPARTMENT OF COMPUTER SCIENCE
dc.contributor.departmentDEPT OF COMPUTER SCIENCE
dc.description.doi10.1109/TVCG.2016.2525724
dc.description.sourcetitleIEEE Transactions on Visualization and Computer Graphics
dc.description.volume23
dc.description.issue2
dc.description.page1056-1069
dc.published.statePublished
Appears in Collections:Staff Publications
Elements

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

CLOSED

None

SCOPUSTM   
Citations

2
checked on Aug 12, 2022

Page view(s)

35
checked on Aug 18, 2022

Download(s)

3
checked on Aug 18, 2022

Google ScholarTM

Check

Altmetric


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