{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,23]],"date-time":"2024-09-23T04:25:48Z","timestamp":1727065548607},"reference-count":21,"publisher":"Institute of Electronics, Information and Communications Engineers (IEICE)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IEICE Trans. Fundamentals"],"published-print":{"date-parts":[[2022,3,1]]},"DOI":"10.1587\/transfun.2021vlp0016","type":"journal-article","created":{"date-parts":[[2021,9,1]],"date-time":"2021-09-01T22:08:44Z","timestamp":1630534124000},"page":"459-467","source":"Crossref","is-referenced-by-count":2,"title":["A Hardware Oriented Approximate Convex Hull Algorithm and its FPGA Implementation"],"prefix":"10.1587","volume":"E105.A","author":[{"given":"Tatsuma","family":"MORI","sequence":"first","affiliation":[{"name":"Graduate School of Engineering, Nagasaki University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Taito","family":"MANABE","sequence":"additional","affiliation":[{"name":"Graduate School of Engineering, Nagasaki University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yuichiro","family":"SHIBATA","sequence":"additional","affiliation":[{"name":"Graduate School of Engineering, Nagasaki University"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"532","reference":[{"key":"1","doi-asserted-by":"crossref","unstructured":"[1] T. Mori, T. Manabe, and Y. Shibata, \u201cFast and memory efficient approximated convex hull computation with FPGA,\u201d Proc. International Symposium on Computing and Networking (CANDAR), 2020. 10.1109\/candar51075.2020.00031","DOI":"10.1109\/CANDAR51075.2020.00031"},{"key":"2","unstructured":"[2] S. Ramaswami, \u201cConvex hulls: Complexity and applications (a survey),\u201d Technical Report, University of Pennsylvania, 1993."},{"key":"3","unstructured":"[3] \u201cQhull,\u201d http:\/\/qhull.org\/, accessed March 1, 2021."},{"key":"4","doi-asserted-by":"publisher","unstructured":"[4] W. Eddy, \u201cA new convex hull algorithm for planar sets,\u201d ACM Trans. Math. Softw., vol.3, no.4, pp.398-403, 1977. 10.1145\/355759.355766","DOI":"10.1145\/355759.355766"},{"key":"5","doi-asserted-by":"publisher","unstructured":"[5] C.B. Barber, D.P. Dobkin, and H.T. Huhdanpaa, \u201cThe quickhull algorithm for convex hulls,\u201d ACM Trans. Math. Softw., vol.22, no.4, pp.469-483, 1996. 10.1145\/235815.235821","DOI":"10.1145\/235815.235821"},{"key":"6","doi-asserted-by":"publisher","unstructured":"[6] G. Mei, \u201cCudaChain: An alternative algorithm for finding 2D convex hulls on the GPU,\u201d SpringerPlus, vol.5, pp.1-26, 2016. 10.1186\/s40064-016-2284-4","DOI":"10.1186\/s40064-016-2284-4"},{"key":"7","doi-asserted-by":"publisher","unstructured":"[7] A.A. Melkman, \u201cOn-line construction of the convex hull of a simple polyline,\u201d Inform. Process. Lett., vol.25, no.1, pp.11-12, 1987. 10.1016\/0020-0190(87)90086-x","DOI":"10.1016\/0020-0190(87)90086-X"},{"key":"8","doi-asserted-by":"crossref","unstructured":"[8] S. Srungarapu, D.P. Reddy, K. Kothapalli, and P.J. Narayanan, \u201cFast two dimensional convex hull on the GPU,\u201d International Conference on Advanced Information Networking and Applications Workshop, pp.7-12, 2011. 10.1109\/waina.2011.64","DOI":"10.1109\/WAINA.2011.64"},{"key":"9","unstructured":"[9] D. Srikanth, P. Reddy, K. Kothapalli, R. Govindarajulu, and P.J. Narayanan, \u201cParallelizing two dimensional convex hull on NVIDIA GPU and Cell BE,\u201d International Conference on High Performance Computing, pp.1-5, 2009."},{"key":"10","unstructured":"[10] S. Tzeng and J.D. Owens, \u201cFinding convex hulls using Quickhull on the GPU,\u201d arXiv preprint arXiv:1201.2936, 2012."},{"key":"11","unstructured":"[11] K. Kanazawa, K. Kemmotsu, Y. Mori, N. Aibe, and M. Yasunaga, \u201cHigh-speed calculation of convex hull in 2D images using FPGA,\u201d Proc. International Conference on Parallel Computing (ParCo), pp.532-542, 2015. 10.3233\/978-1-61499-621-7-533"},{"key":"12","doi-asserted-by":"publisher","unstructured":"[12] A.M. Andrew, \u201cAnother efficient algorithm for convex hulls in two dimensions,\u201d Inform. Process. Lett., vol.9, no.5, pp.216-219, 1979. 10.1016\/0020-0190(79)90072-3","DOI":"10.1016\/0020-0190(79)90072-3"},{"key":"13","doi-asserted-by":"crossref","unstructured":"[13] R.L. Graham, \u201cAn efficient algorithm for determining the convex hull of a finite planar set,\u201d Inform. Process. Lett., vol.1, no.4, pp.132-133, 1972. 10.1016\/0020-0190(72)90045-2","DOI":"10.1016\/0020-0190(72)90045-2"},{"key":"14","unstructured":"[14] L. Kavan, I. Kolingerova, and J. Zara, \u201cFAST approximation of convex hull,\u201d The 2nd International Association of Science and Technology for Development International Conference on Advances in Computer Science and Technology, pp.101-104, 2006."},{"key":"15","doi-asserted-by":"publisher","unstructured":"[15] J.L. Bentley, G.M. Faust, and F.P. Preparata, \u201cApproximation algorithms for convex hulls,\u201d Commun. ACM, vol.25, no.1, pp.64-68, 1982. 10.1145\/358315.358392","DOI":"10.1145\/358315.358392"},{"key":"16","doi-asserted-by":"publisher","unstructured":"[16] Z. Hussain, \u201cA fast approximation to a convex hull,\u201d Pattern Recogn. Lett., vol.8, no.5, pp.289-294, 1988. 10.1016\/0167-8655(88)90077-3","DOI":"10.1016\/0167-8655(88)90077-3"},{"key":"17","doi-asserted-by":"publisher","unstructured":"[17] M.Z. Hossain and M.A. Amin, \u201cOn constructing approximate convex hull,\u201d American Journal of Computational Mathematics, vol.3, no.1A, pp.11-17, 2013. 10.4236\/ajcm.2013.31a003","DOI":"10.4236\/ajcm.2013.31A003"},{"key":"18","unstructured":"[18] \u201cThe Standford 3D Scanning Repository,\u201d http:\/\/www.graphics.stanford.edu\/data\/3Dscanrep\/, accessed July 2, 2021."},{"key":"19","unstructured":"[19] \u201cGIT Large Geometry Models Archive,\u201d https:\/\/www.cc.gatech.edu\/projects\/large_models\/, accessed July 2, 2021."},{"key":"20","doi-asserted-by":"crossref","unstructured":"[20] J. Qin, G. Mei, S. Cuomo, S. Guo, and Y. Li, \u201cCudaCHPre2D: A straightforward preprocessing approach for accelerating 2D convex hull computations on the GPU,\u201d Concurrency and Computation Practice and Experience, vol.32, no.4, pp.1-12, 2019.","DOI":"10.1002\/cpe.5229"},{"key":"21","unstructured":"[21] \u201cComputing the convex hull on GPU,\u201d https:\/\/timiskhakov.github.io\/posts\/computing-the-convex-hull-on-gpu, accessed July 2, 2021."}],"container-title":["IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.jstage.jst.go.jp\/article\/transfun\/E105.A\/3\/E105.A_2021VLP0016\/_pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,3,5]],"date-time":"2022-03-05T03:24:19Z","timestamp":1646450659000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.jstage.jst.go.jp\/article\/transfun\/E105.A\/3\/E105.A_2021VLP0016\/_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,3,1]]},"references-count":21,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022]]}},"URL":"https:\/\/doi.org\/10.1587\/transfun.2021vlp0016","relation":{},"ISSN":["0916-8508","1745-1337"],"issn-type":[{"value":"0916-8508","type":"print"},{"value":"1745-1337","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,3,1]]},"article-number":"2021VLP0016"}}