Please use this identifier to cite or link to this item:
https://doi.org/10.1145/2513109.2513112
DC Field | Value | |
---|---|---|
dc.title | GHull: A GPU algorithm for 3D convex hull | |
dc.contributor.author | Gao, M. | |
dc.contributor.author | Cao, T.-T. | |
dc.contributor.author | Nanjappa, A. | |
dc.contributor.author | Tan, T.-S. | |
dc.contributor.author | Huang, Z. | |
dc.date.accessioned | 2014-07-04T03:09:40Z | |
dc.date.available | 2014-07-04T03:09:40Z | |
dc.date.issued | 2013 | |
dc.identifier.citation | Gao, M., Cao, T.-T., Nanjappa, A., Tan, T.-S., Huang, Z. (2013). GHull: A GPU algorithm for 3D convex hull. ACM Transactions on Mathematical Software 40 (1) : -. ScholarBank@NUS Repository. https://doi.org/10.1145/2513109.2513112 | |
dc.identifier.issn | 00983500 | |
dc.identifier.uri | http://scholarbank.nus.edu.sg/handle/10635/77862 | |
dc.description.abstract | A novel algorithm is presented to compute the convex hull of a point set in R3 using the graphics processing unit (GPU). By exploiting the relationship between the Voronoi diagram and the convex hull, the algorithm derives the approximation of the convex hull from the former. The other extreme vertices of the convex hull are then found by using a two-round checking in the digital and the continuous space successively. The algorithm does not need explicit locking or any other concurrency control mechanism, thus it can maximize the parallelism available on the modern GPU. The implementation using the CUDA programming model on NVIDIA GPUs is exact and efficient. The experiments show that it is up to an order of magnitude faster than other sequential convex hull implementations running on the CPU for inputs of millions of points. The works demonstrate that the GPU can be used to solve nontrivial computational geometry problems with significant performance benefit. © 2013 ACM. | |
dc.description.uri | http://libproxy1.nus.edu.sg/login?url=http://dx.doi.org/10.1145/2513109.2513112 | |
dc.source | Scopus | |
dc.subject | GPGPU | |
dc.subject | Star splaying | |
dc.subject | Voronoi diagram | |
dc.type | Article | |
dc.contributor.department | COMPUTER SCIENCE | |
dc.description.doi | 10.1145/2513109.2513112 | |
dc.description.sourcetitle | ACM Transactions on Mathematical Software | |
dc.description.volume | 40 | |
dc.description.issue | 1 | |
dc.description.page | - | |
dc.description.coden | ACMSC | |
dc.identifier.isiut | 000326289800003 | |
Appears in Collections: | Staff Publications |
Show simple item record
Files in This Item:
There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.