{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2021,10,26]],"date-time":"2021-10-26T21:47:33Z","timestamp":1635284853316},"reference-count":36,"publisher":"Association for Computing Machinery (ACM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM Trans. Math. Softw."],"published-print":{"date-parts":[[1996,12]]},"abstract":"The convex hull of a set of points is the smallest convex set that contains the points. This article presents a practical convex hull algorithm that combines the two-dimensional Quickhull algorithm with the general-dimension Beneath-Beyond Algorithm. It is similar to the randomized, incremental algorithms for convex hull and delaunay triangulation. We provide empirical evidence that the algorithm runs faster when the input contains nonextreme points and that it used less memory. computational geometry algorithms have traditionally assumed that input sets are well behaved. When an algorithm is implemented with floating-point arithmetic, this assumption can lead to serous errors. We briefly describe a solution to this problem when computing the convex hull in two, three, or four dimensions. The output is a set of \u201cthick\u201d facets that contain all possible exact convex hulls of the input. A variation is effective in five or more dimensions.<\/jats:p>","DOI":"10.1145\/235815.235821","type":"journal-article","created":{"date-parts":[[2002,7,27]],"date-time":"2002-07-27T11:29:03Z","timestamp":1027769343000},"page":"469-483","source":"Crossref","is-referenced-by-count":2886,"title":["The quickhull algorithm for convex hulls"],"prefix":"10.1145","volume":"22","author":[{"given":"C. Bradford","family":"Barber","sequence":"first","affiliation":[{"name":"Univ. of Minnesota, Minneapolis"}]},{"given":"David P.","family":"Dobkin","sequence":"additional","affiliation":[{"name":"Princeton Univ., Princeton, NJ"}]},{"given":"Hannu","family":"Huhdanpaa","sequence":"additional","affiliation":[{"name":"Configured Energy Systems, Inc., Plymouth, MN"}]}],"member":"320","reference":[{"key":"e_1_2_1_1_1","first-page":"153","article-title":"Determination and evaluation of support structures in layered manufacturing","volume":"5","author":"ALLEN S.","year":"1995","journal-title":"J. Des. Manufactur."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/116873.116880"},{"key":"e_1_2_1_3_1","first-page":"20","volume-title":"Proceedings of the llth Annual ACM Symposium on Computational Geomett3,. ACM","author":"BREMNER D.","year":"1995"},{"key":"e_1_2_1_5_1","volume-title":"the 4th JPL Airborne Geoscience Workshop (Washington, D.C.). JPL, Pasadena, Calif.","author":"BOARDMAN J.","year":"1993"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(93)90024-N"},{"issue":"5","key":"e_1_2_1_7_1","doi-asserted-by":"crossref","first-page":"1000","DOI":"10.2514\/3.21497","article-title":"Closed-form solutions to constrained control allocation problem","volume":"18","author":"BORDIGNON K. A.","year":"1995","journal-title":"J. Guidance Contr. Dynam."},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1016\/0020-0190(79)90074-7","article-title":"Voronoi diagrams from convex hulls","volume":"9","author":"BROWN D.","year":"1979","journal-title":"Inf. Process. Lett."},{"key":"e_1_2_1_9_1","doi-asserted-by":"crossref","first-page":"296","DOI":"10.1016\/0020-0190(78)90021-2","article-title":"Convex hull of a finite set of points in two dimensions","volume":"7","author":"BYKAT A.","year":"1978","journal-title":"Inf. Process. Lett."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/321556.321564"},{"key":"e_1_2_1_11_1","article-title":"Randomizing an output-sensitive convex hull algorithm in three dimensions","author":"CHAZELLE B.","year":"1992","journal-title":"Tech. Rep. TR-361-92, Princeton Univ., Princeton, N.J."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187740"},{"key":"e_1_2_1_13_1","first-page":"387","volume-title":"Proceedings of the 31st IEEE Symposium on Foundations of Computer Science. IEEE","author":"CLARKSON K.L.","year":"1992"},{"key":"e_1_2_1_14_1","unstructured":"CLARKSON K. L. 1995. A program for convex hulls. ATT Murray Hill N.J. Available as http:\/\/netlib.att.com\/netlib\/voronoi\/hull.html. CLARKSON K. L. 1995. A program for convex hulls. ATT Murray Hill N.J. Available as http:\/\/netlib.att.com\/netlib\/voronoi\/hull.html."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/0925-7721(93)90009-U"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-8396(92)90044-P"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/355759.355766"},{"key":"e_1_2_1_19_1","first-page":"43","volume-title":"Proceedings of the Symposium on Computational Geometl),. ACM","author":"EDELSBRUNNER H.","year":"1992"},{"key":"e_1_2_1_20_1","volume-title":"the 30th Annual Symposium on the Foundations of Computer Science. IEEE","author":"FORTUNE S.","year":"1989"},{"key":"e_1_2_1_21_1","volume-title":"Directions in Geometric Computing","author":"FORTUNE S."},{"key":"e_1_2_1_22_1","series-title":"Lecture Notes in Computer Science","volume-title":"Double description method revisited","author":"FUKUDA K."},{"key":"e_1_2_1_23_1","doi-asserted-by":"crossref","first-page":"262","DOI":"10.1093\/comjnl\/22.3.262","article-title":"Constructing the convex hull of a set of points in the plane","volume":"22","author":"GREEN P.","year":"1979","journal-title":"Comput. J."},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of the 7th Symposium in Pure Mathematics of the American Mathematical Society, Symposium on Convexity. AMS, Providence, R.I., 233-270","author":"GR BAUM","year":"1961"},{"key":"e_1_2_1_25_1","first-page":"534","article-title":"Randomized incremental construction of Delaunay and Voronoi diagrams","volume":"9","author":"GUIBAS L.","year":"1992","journal-title":"Algorithmica"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-8396(91)90038-D"},{"key":"e_1_2_1_27_1","volume-title":"Dept. of Mathematics, Univ. of Oklahoma","author":"KALLAY M."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/0215021"},{"key":"e_1_2_1_29_1","volume-title":"Proceedings of the IBM Scientific Computing Symposium: Combinatorial Problems. IBM, Armonk, N.Y., 123-158","author":"KLEE V.","year":"1966"},{"key":"e_1_2_1_30_1","first-page":"197","volume-title":"Proceedings of the Symposium on Computational Geometry. ACM","author":"LI Z.","year":"1990"},{"key":"e_1_2_1_31_1","first-page":"51","volume-title":"Eds. Annals of Mathematics","volume":"8","author":"MOTZKIN T. S.","year":"1953"},{"key":"e_1_2_1_32_1","volume-title":"An Introduction through Randomized Algorithms","author":"MULMULEY D."},{"issue":"8","key":"e_1_2_1_33_1","doi-asserted-by":"crossref","first-page":"4694","DOI":"10.1063\/1.361708","article-title":"Irregular grain structure in micromagnetic simulation","volume":"79","author":"PORTER D.","year":"1996","journal-title":"J. Appl. Physics"},{"key":"e_1_2_1_34_1","volume-title":"Computational GeometlT. An Introduction","author":"PREPARATA D. F."},{"key":"e_1_2_1_35_1","first-page":"404","volume-title":"Proceedings of the 18th ACM Symposium on the TheolT of Computing. ACM","author":"SEIDEL R.","year":"1986"},{"key":"e_1_2_1_36_1","volume-title":"the 1st Workshop on Applied Computational GeometlT. ACM","author":"SHEWCHUK J.R.","year":"1996"},{"key":"e_1_2_1_37_1","first-page":"209","volume-title":"3rd International Symposium (ISSAC '92)","volume":"650","author":"SUGIHARA K.","year":"1992"},{"key":"e_1_2_1_39_1","first-page":"1","volume-title":"the IEEE International Symposium on Circuits and Systems. IEEE","author":"ZHANG B.","year":"1994"}],"container-title":["ACM Transactions on Mathematical Software"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/235815.235821","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,2,28]],"date-time":"2021-02-28T16:39:02Z","timestamp":1614530342000},"score":1,"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996,12]]},"references-count":36,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1996,12]]}},"alternative-id":["10.1145\/235815.235821"],"URL":"http:\/\/dx.doi.org\/10.1145\/235815.235821","relation":{},"ISSN":["0098-3500","1557-7295"],"issn-type":[{"value":"0098-3500","type":"print"},{"value":"1557-7295","type":"electronic"}],"subject":["Applied Mathematics","Software"],"published":{"date-parts":[[1996,12]]}}}