{"entities":{"Q919797":{"pageid":921645,"ns":120,"title":"Item:Q919797","lastrevid":49411957,"modified":"2026-01-07T03:01:17Z","type":"item","id":"Q919797","labels":{"en":{"language":"en","value":"An efficient and numerically correct algorithm for the 2D convex hull problem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4162230"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q919797$BD24314C-E8E7-4087-9E51-89775D72FADE","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"49ba3ab23f05edc1097f0ea5a0bda890d8b2a961","datavalue":{"value":{"text":"An efficient and numerically correct algorithm for the 2D convex hull problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q919797$F810533E-2E07-409F-AB65-5F1A572DEED7","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"50d859f65f5251125e0e328757d792da3153f56c","datavalue":{"value":"0707.65110","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q919797$4E8BFB24-EE01-4E13-8F25-CBE54DFBC4F8","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"926871a937ae43efdb5a118e92086786fe5d2165","datavalue":{"value":"10.1007/BF02017351","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q919797$CCCD592A-6124-43A6-B91D-A10C669C6B93","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"df271c54073b0eee4ceb91a32bc281b17926dc81","datavalue":{"value":{"entity-type":"item","numeric-id":919795,"id":"Q919795"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q919797$94D57110-868C-4F8B-9F78-2788CA62531D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d7c2f541323f67bb5db8f30d15d32ab8f3b648b2","datavalue":{"value":{"entity-type":"item","numeric-id":919796,"id":"Q919796"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q919797$06D06CF0-752A-4C22-B3C5-95835731437C","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"e560271c921b84b65a9b7f0d3fa6830623f8af8b","datavalue":{"value":{"entity-type":"item","numeric-id":188629,"id":"Q188629"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q919797$5A9EC017-C381-4C29-B81B-B5F2CF865D6A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"70d2fbf8bcd48a5ca1ac752985098b379d0dbb65","datavalue":{"value":{"time":"+1990-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q919797$C8019E84-D18A-4C69-BD1B-4C0755B7E00A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"f097ef77b310329d8900dbad3261708ee4ba97aa","datavalue":{"value":"This paper is concerned with the determination of the boundary of the convex hull of a finite set of points in the plane. It presents an algorithm which is based on the algorithm by \\textit{S. G. Akl} and \\textit{G. T. Toussaint} [Inform. Processing Lett. 7, 219-222 (1978; Zbl 0392.52003)] and the Merge Hull algorithm described by \\textit{F. P. Preparata} and \\textit{M. I. Shamos} [Computational geometry, an introduction (1985; Zbl 0575.68059)]. Its numerical correctness is ensured by using special routines for interval arithmetic and multiple precision arithmetic. Its worst-case running time behaviour is O(N log N) with a small constant multiplier where N denotes the number of points and it has expected linear time performance for various kinds of input patterns. For many input point patterns it seems to run faster than any currently known plane convex hull algorithms.    Theoretically, the algorithm by \\textit{D. G. Kirkpatrick} and \\textit{R. Seidel} [SIAM J. Comput. 15, 287-299 (1986; Zbl 0589.68035)] with an asymptotical worst-case running behaviour of O(N log h) (where h is the number of the edges of the convex hull) seems to be better, but has not yet been studied practically. Also its expected performance has not been analyzed.","type":"string"},"datatype":"string"},"type":"statement","id":"Q919797$723C57C5-B6A6-4D4A-BABA-4B2B99332756","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"2ce72165d993b0b8ed97728d731d2db2473b9554","datavalue":{"value":"65D18","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q919797$9DA98124-143D-44AD-823B-09799CE9E61F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4d2aa49789d35e35613e1a84ce4788bfee1559e6","datavalue":{"value":"65G30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q919797$B83A3979-836B-4E54-83E8-6264F0EC809E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"719fd2949b80c8cc7a58cbc4ca1d7d0d3b69123f","datavalue":{"value":"52-04","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q919797$F20D2ADF-3026-409B-895B-1EA0311068A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e5762e9b09407c15760c5fa5cac71c82c32bf230","datavalue":{"value":"52A10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q919797$CB950E02-554D-4755-93C2-1BF66F66A0FA","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"1da9fa9649607cea4f7feaadd1c44b11f6d95f9f","datavalue":{"value":"4162230","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q919797$1646EF0A-0536-43BD-8B37-78FDB5CC76D8","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c1a501ddc157174325e315d5af551c272638f4d8","datavalue":{"value":"2D convex hull problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q919797$5E53CF72-5C6F-4A2B-8890-05D7702E4E1C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6cf14a92d27902f0cdd14456d83bc321cb8d2bc9","datavalue":{"value":"bucketing techniques","type":"string"},"datatype":"string"},"type":"statement","id":"Q919797$B0443A60-21FD-4373-A263-9BD28CBE69C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c3c55a2f0ea894ac5837ca03100bf1a9e0e51bca","datavalue":{"value":"point elimination techniques","type":"string"},"datatype":"string"},"type":"statement","id":"Q919797$837E0E05-E50D-4C6F-87EB-6FC74F534055","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6a5de1f9fe3c2294d5c4949873c9507c3dbae397","datavalue":{"value":"boundary of the convex hull","type":"string"},"datatype":"string"},"type":"statement","id":"Q919797$61FC1DE6-A299-4ACE-A72C-EF1878BEDBA4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6c8cb1024be649c50b04a584552fd7b4d5f5bf6f","datavalue":{"value":"finite set of points","type":"string"},"datatype":"string"},"type":"statement","id":"Q919797$577BEDA3-2444-4D9D-960B-05CD2EB4516D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"36bf203f9ce55fd48abf0c126ca3c57f9d49bb5a","datavalue":{"value":"Merge Hull algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q919797$29A41861-2F28-4AC3-A63E-CA952495E29E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b44e0460de8b89a3695e54806f9b749b49a67a49","datavalue":{"value":"interval arithmetic","type":"string"},"datatype":"string"},"type":"statement","id":"Q919797$5307F054-4189-41C7-8A68-0BAAF58DA0D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"81d6bb68baad799efc438ed735dd33ab35391aae","datavalue":{"value":"multiple precision arithmetic","type":"string"},"datatype":"string"},"type":"statement","id":"Q919797$BD5F7A00-3B0C-47A8-818E-5995A403286E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"50a428a8dd473ec6c7d2790a49dd0e5a4e691969","datavalue":{"value":"worst-case running time behaviour","type":"string"},"datatype":"string"},"type":"statement","id":"Q919797$C7FAE24A-B790-4167-BFD3-7B3B00206FCB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f5c11a8dabfe663e45e6bbda62613df4cd3eed65","datavalue":{"value":"plane convex hull algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q919797$D64D5EC4-85F8-4906-8E40-98D886F1F450","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"1602a325d3d2fc4285dfc7653c52bde7eb00c007","datavalue":{"value":{"entity-type":"item","numeric-id":579218,"id":"Q579218"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q919797$ACCB68D4-2730-4C75-A742-2A14A791F3E1","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q919797$B1543590-C6BD-4257-8A12-E5EB0DC291E2","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"e10e07a6ede216b8114199cacaae38abca26a267","datavalue":{"value":{"entity-type":"item","numeric-id":3716294,"id":"Q3716294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q919797$4718B669-E253-4D5B-B994-F53FE05F28DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"340ea97c0f2f383d364057042ebc9f9438fcc85a","datavalue":{"value":{"entity-type":"item","numeric-id":4091421,"id":"Q4091421"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q919797$50232097-337D-4920-9385-B8373F051419","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c642d3ed5f726891145ddb88553fa6112586442a","datavalue":{"value":{"entity-type":"item","numeric-id":1251805,"id":"Q1251805"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q919797$4C9DF778-F82B-4E9B-B478-A31C36CB832D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ab974389d5e8071746e17da50642de7dbdde25d2","datavalue":{"value":{"entity-type":"item","numeric-id":1070524,"id":"Q1070524"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q919797$9773692D-B99B-42BA-8E16-3734859D16F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"200564e1031f8898cdeea2e3c2835fdbdcd779d2","datavalue":{"value":{"entity-type":"item","numeric-id":3919102,"id":"Q3919102"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q919797$D559693F-02EA-4229-84EB-6D171BCD94C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d2f37c3ffc595c99b9b79b892133b20fbefc5a71","datavalue":{"value":{"entity-type":"item","numeric-id":1256853,"id":"Q1256853"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q919797$94BA3A43-BB5B-4CF2-8407-F85DCA9C533C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f545c2db529ae3050e745aa3193c438be89c47fc","datavalue":{"value":{"entity-type":"item","numeric-id":4151725,"id":"Q4151725"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q919797$8DD780A8-9827-4EB9-BD73-A75BF9B0C23A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4b93cbcfe92914798c52148f95cc353b5e256c5a","datavalue":{"value":{"entity-type":"item","numeric-id":2552382,"id":"Q2552382"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q919797$539859AA-2A31-488F-AD2B-FB6C9E4524A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6ae3d76a9857dc20a0ba6e1c35ab466fb19d6b86","datavalue":{"value":{"entity-type":"item","numeric-id":3206332,"id":"Q3206332"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q919797$227669C9-C5A6-4A3F-A65C-23F9876F5C80","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"beec7e889a9c95b1a37f6168453aee45724b16e0","datavalue":{"value":{"entity-type":"item","numeric-id":3832090,"id":"Q3832090"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q919797$6C273DD6-EA4A-472C-A2E2-41809BC5775E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cf593863ead8137760e8e498990b7377f26076e5","datavalue":{"value":{"entity-type":"item","numeric-id":2559148,"id":"Q2559148"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q919797$B6E73F39-0576-4A52-8269-A93475050C80","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b90f074f966bfe2cf45005f01ba35bf5c6bde89c","datavalue":{"value":{"entity-type":"item","numeric-id":3718154,"id":"Q3718154"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q919797$F09F98E5-34A3-4FBE-A443-B00A94E8DE2B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"07265a1e36253f3446e2d6661c182bfed2a0f5a0","datavalue":{"value":{"entity-type":"item","numeric-id":799379,"id":"Q799379"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q919797$7CAC6ABD-C780-46CD-872E-C0B2F8AE1F4D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"08bbfa2750c080ec67d6b7bc35b58e0a9bc36c96","datavalue":{"value":{"entity-type":"item","numeric-id":3694703,"id":"Q3694703"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q919797$0F248FEA-33BA-4BE1-B244-1C1A0ABA6BA4","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"0becc545db32bc433a3a11b1478e7f3af17c3b52","datavalue":{"value":"https://doi.org/10.1007/bf02017351","type":"string"},"datatype":"url"},"type":"statement","id":"Q919797$AAA70D29-BC08-4FC9-BE95-31F676EE19E8","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"f4f1ddc80dc07e0741931f0fec9819e805e20107","datavalue":{"value":"W1972379785","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q919797$53978332-F08A-410C-B432-67E06D676E8D","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1c3ca32f5f97847f9af6d01abbe4089d80f37592","datavalue":{"value":{"entity-type":"item","numeric-id":4371114,"id":"Q4371114"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f6aee6192e6c501361bad1ebe51ee2fcc4c5cfac","datavalue":{"value":{"amount":"+0.8841612339019775","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q919797$74C6058A-D4A6-4120-A8BA-EFAAE90212DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"085cc92fb57b946dbf7e8c5e690875f6ecc4f2dd","datavalue":{"value":{"entity-type":"item","numeric-id":4366880,"id":"Q4366880"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f6aee6192e6c501361bad1ebe51ee2fcc4c5cfac","datavalue":{"value":{"amount":"+0.8841612339019775","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q919797$5703B9EB-80B5-4867-89DB-28A4756391FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3d48c62fb924c08961120ceca9fb248e94385459","datavalue":{"value":{"entity-type":"item","numeric-id":4682192,"id":"Q4682192"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"486800f683ffb638904406150dc38ddb0c5832d5","datavalue":{"value":{"amount":"+0.8792790770530701","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q919797$3F5E72F5-E586-48DA-908C-ADA89247BE34","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e041137b060402764fae283749f908f5c6dfca4f","datavalue":{"value":{"entity-type":"item","numeric-id":3718154,"id":"Q3718154"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bc071caa93bbff17d3fe3146a78015e0f948331f","datavalue":{"value":{"amount":"+0.8678843975067139","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q919797$37EDFAB3-C878-45C8-A683-258DA8443346","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"26f56b08423357bff1210d8bd483d8abe24f08aa","datavalue":{"value":{"entity-type":"item","numeric-id":1070524,"id":"Q1070524"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"108fb0cf8b93cbca0f6960d2421944847b8735e1","datavalue":{"value":{"amount":"+0.8638752102851868","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q919797$1BAE2ED4-1140-4EF0-8BA3-70AFF899511B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:919797","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:919797"}}}}}