{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,7]],"date-time":"2025-07-07T07:26:11Z","timestamp":1751873171584},"reference-count":27,"publisher":"World Scientific Pub Co Pte Lt","issue":"02","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Comput. Geom. Appl."],"published-print":{"date-parts":[[1998,4]]},"abstract":"<jats:p> We present a robust implementation of the Beneath-Beyond algorithm for computing convex hulls in arbitrary dimension. Certain techniques used are of independent interest in the implementation of geometric algorithms. In particular, two important, and often complementary, issues are studied, namely exact arithmetic and degeneracy. We focus on integer arithmetic and propose a general and efficient method for its implementation based on modular arithmetic. We suggest that probabilistic modular arithmetic may be of wide interest, as it combines the advantages of modular arithmetic with the speed of randomization. The use of perturbations as a method to cope with input degeneracy is also illustrated. A computationally efficient scheme is implemented which, moreover, greatly simplifies the task of programming. We concentrate on postprocessing, often perceived as the Achilles' heel of perturbations. Experimental results illustrate the dependence of running time on the various input parameters and attempt a comparison with existing programs. Lastly, we discuss the visualization capabilities of our software and illustrate them for problems in computational algebraic geometry. All code is publicly available. <\/jats:p>","DOI":"10.1142\/s0218195998000126","type":"journal-article","created":{"date-parts":[[2003,7,22]],"date-time":"2003-07-22T11:10:21Z","timestamp":1058872221000},"page":"223-253","source":"Crossref","is-referenced-by-count":16,"title":["A Complete Implementation for Computing General Dimensional Convex Hulls"],"prefix":"10.1142","volume":"08","author":[{"given":"Ioannis Z.","family":"Emiris","sequence":"first","affiliation":[{"name":"INRIA, B.P. 93, 06902 Sophia-Antipolis, France"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"p_5","doi-asserted-by":"publisher","DOI":"10.1007\/BF02293035"},{"key":"p_6","doi-asserted-by":"publisher","DOI":"10.1145\/322092.322095"},{"key":"p_9","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1992.267751"},{"key":"p_10","doi-asserted-by":"publisher","DOI":"10.1016\/0925-7721(93)90009-U"},{"key":"p_12","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187740"},{"key":"p_13","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(08)80013-2"},{"key":"p_14","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-57155-8_258"},{"key":"p_15","first-page":"93","author":"Dobkin D.","year":"1988","journal-title":"Proc. ACM Symp. on Computational Geometry, pages"},{"key":"p_17","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840438"},{"key":"p_20","doi-asserted-by":"publisher","DOI":"10.1145\/77635.77639"},{"key":"p_21","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(86)80020-7"},{"key":"p_25","doi-asserted-by":"publisher","DOI":"10.1006\/jsco.1995.1041"},{"key":"p_26","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792235918"},{"key":"p_28","first-page":"163","author":"Fortune S.","year":"1993","journal-title":"Proc. ACM Symp. on Computational Geometry, pages"},{"key":"p_30","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1995-1297471-4"},{"key":"p_31","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(85)90049-0"},{"key":"p_33","first-page":"602","author":"Lin M.C.","year":"1994","journal-title":"Proc. IEEE Conf. Robotics and Automation, pages"},{"key":"p_34","doi-asserted-by":"publisher","DOI":"10.1006\/jsco.1993.1009"},{"key":"p_36","author":"Miicke E.P.","journal-title":"Int'l J. Computational Geometry & Applications, this issue."},{"key":"p_39","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/37.1.35"},{"key":"p_40","doi-asserted-by":"publisher","DOI":"10.1007\/BF02574699"},{"key":"p_41","first-page":"3","volume":"775","author":"Seidel R.","year":"1994","journal-title":"Proc. 11th Symp. Theoret. Aspects Computer Science, LNCS"},{"key":"p_43","doi-asserted-by":"publisher","DOI":"10.1137\/0731049"},{"key":"p_44","doi-asserted-by":"crossref","unstructured":"3. von zur Gathen, \"Algebraic complexity theory,\" InJ. Traub, editor, Annual Review of Computer Science, pages 317-347. Annual Reviews, Palo Alto, Cal., 1988.","DOI":"10.1146\/annurev.cs.03.060188.001533"},{"key":"p_47","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(90)90016-E"},{"key":"p_48","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(08)80069-7"},{"key":"p_49","first-page":"405","author":"Yap C.-K.","year":"1993","journal-title":"Proc. Canadian Conf. on Computational Geometry, pages"}],"container-title":["International Journal of Computational Geometry &amp; Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218195998000126","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T00:31:48Z","timestamp":1565137908000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218195998000126"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,4]]},"references-count":27,"journal-issue":{"issue":"02","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[1998,4]]}},"alternative-id":["10.1142\/S0218195998000126"],"URL":"https:\/\/doi.org\/10.1142\/s0218195998000126","relation":{},"ISSN":["0218-1959","1793-6357"],"issn-type":[{"value":"0218-1959","type":"print"},{"value":"1793-6357","type":"electronic"}],"subject":[],"published":{"date-parts":[[1998,4]]}}}