{"entities":{"Q1070524":{"pageid":1081276,"ns":120,"title":"Item:Q1070524","lastrevid":69564498,"modified":"2026-04-13T07:52:16Z","type":"item","id":"Q1070524","labels":{"en":{"language":"en","value":"Some performance tests of convex hull algorithms"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3935873"}},"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":"Q1070524$BBAC39CE-2DDC-477D-A9BC-A97E5D43CC0C","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"513b2414e2278ce40837e57e29d8f143ad359ae1","datavalue":{"value":{"text":"Some performance tests of convex hull algorithms","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1070524$9F000C59-BA87-4C9E-A7FD-7AB77859358A","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"f1d1e78672f247c797dccc1da213db278bb29d2c","datavalue":{"value":"0584.52002","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1070524$0EEC892A-0F24-4293-8218-49ECC16259FD","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c17aeac5f6b40a8ee10525b44549c751a2793e25","datavalue":{"value":"10.1007/BF01934510","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1070524$44249847-A31A-41A7-B463-46A93AF15484","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"d6f2ef08ffc92e794a3c62964c0ff220b8eb3d37","datavalue":{"value":{"entity-type":"item","numeric-id":1064784,"id":"Q1064784"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1070524$5D80428F-A113-459F-8D38-88F184E73662","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"54ed762b7716bd4824ac256c27cc02ada150e6bd","datavalue":{"value":{"entity-type":"item","numeric-id":1064783,"id":"Q1064783"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1070524$E4691FE0-0D32-4B4E-8867-227AFBDC218A","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":"Q1070524$E51DA157-8429-4F89-81A2-F43392382DE2","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2ee0f220147ae8bc749a64db56839865dbc4f127","datavalue":{"value":{"time":"+1984-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":"Q1070524$58AD46A7-5272-406B-B2F4-3E9F4B7654FE","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"b3a30131395cd80da374fef70402f231cae4ded2","datavalue":{"value":"The authors test the two-dimensional convex hull algorithms of \\textit{R. L. Graham} [Inf. Process. Lett. 1, 132-133 (1972; Zbl 0236.68013)], \\textit{R. A. Jarvis} [Inf. Process. Lett. 2, 18-21 (1973; Zbl 0256.68041)], \\textit{W. F. Eddy}[ACM Trans. math. Software 3, 398-403 (1977; Zbl 0374.68036)] and \\textit{S. G. Akl} and \\textit{G. T. Toussaint} [Inf. Process. Lett. 7, 219-222 (1978; Zbl 0392.52003)], by comparing Fortran implementations of them on four different planar point distributions. Several modifications of both the Graham and Jarvis algorithms are considered. The running times obtained by these experiments indicate that the Graham algorithm is the most convenient on point distributions where most of the points are on or near the boundary of the hull, while the Eddy and Akl-Toussaint algorithms are the bests for uniform distributions of points in the plane. The authors suggest that the design of significantly better convex hull algorithms requires the development of a faster sort algorithm.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1070524$D80B2B6F-C9D5-4A63-A16C-FC09F7CB26BB","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"e5762e9b09407c15760c5fa5cac71c82c32bf230","datavalue":{"value":"52A10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1070524$5E49C421-C902-4075-A204-865CA12E5080","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"719fd2949b80c8cc7a58cbc4ca1d7d0d3b69123f","datavalue":{"value":"52-04","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1070524$0640C2AC-B72B-4888-9618-0D2A7A83BE0B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9ed1e3c6cced595a05b8ae19055521b22405b78a","datavalue":{"value":"68W99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1070524$D57D41EB-37FC-4563-922F-9B39C3E808D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"ddd8cb1932c6bc41681458db5f685a2a286fde55","datavalue":{"value":"52Bxx","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1070524$CCDE1130-FD7F-4326-94B4-357CA1727784","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"91df22b8012030ff005e2269d5a18d8817354822","datavalue":{"value":"3935873","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1070524$7D895AF8-A0A7-4C2D-9E9D-CC396F50E0E4","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"551d108313cfab3a77b395a647aede7021169ebd","datavalue":{"value":"computational geometry","type":"string"},"datatype":"string"},"type":"statement","id":"Q1070524$ACB1884D-061E-4C49-BC77-DAE4D258A989","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ef19eea863e1afbd0df82665507359b4bf5a5618","datavalue":{"value":"geometric sorting","type":"string"},"datatype":"string"},"type":"statement","id":"Q1070524$4C711F92-AA68-4978-8FF0-BC22364A124E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0c25bed9bd7a08de1d511daafd14c254cf16eb5f","datavalue":{"value":"distributive partitioning","type":"string"},"datatype":"string"},"type":"statement","id":"Q1070524$E9BECB28-AB36-4FD3-BF8C-40AD550E986A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"44a1cee927d9c007c205fca1c83bc95235b7e41e","datavalue":{"value":"two-dimensional convex hull algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1070524$C9390ACF-4371-4902-A432-DA941B6CE37E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"46dc5fc64f892a02d9dc1e7403d68c3e83216259","datavalue":{"value":"planar point distributions","type":"string"},"datatype":"string"},"type":"statement","id":"Q1070524$668E802B-59A1-46CB-AAB6-20057FED81B0","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":"Q1070524$80FC070B-E737-40EE-AD04-D54BAC72CE6B","rank":"normal"}],"P223":[{"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":"Q1070524$9FD95EBB-F31D-412C-868E-6518D1756E99","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"28f3b7dc64a740f623cb4c1b0b5cf409101ef0e2","datavalue":{"value":{"entity-type":"item","numeric-id":1252725,"id":"Q1252725"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1070524$569104AA-5199-4A45-B88B-AF79CAC866F4","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":"Q1070524$BFD782A8-280A-4722-9AC6-EFBE67F46D46","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4459c6d067c8685a953bcd48d3985388efa1bc07","datavalue":{"value":{"entity-type":"item","numeric-id":1162815,"id":"Q1162815"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1070524$6C08AB45-13DD-4E16-9773-E97B04D250D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0b70c81afc1baf8946901aee29206ab003de6c11","datavalue":{"value":{"entity-type":"item","numeric-id":1241280,"id":"Q1241280"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1070524$91E84A8F-D3C9-4594-9383-1D06F2845A13","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9afa1000dbd6740ee6125c6c7be3e1a0c005945c","datavalue":{"value":{"entity-type":"item","numeric-id":1251803,"id":"Q1251803"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1070524$E2D84185-C918-4EE6-B888-9A70084B7675","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":"Q1070524$A9777447-5252-47E1-85AF-3EEC042A0723","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":"Q1070524$3E65BC25-E705-47EC-8E26-DBB05E4DF607","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":"Q1070524$1EA66BF7-EAA1-472B-8EE0-A8B9C294504D","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":"Q1070524$9431AC89-59E2-41BD-80BA-D6C149D6FA24","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"288294a596fa9e8ac815daacd2fe0c350d6b539d","datavalue":{"value":{"entity-type":"item","numeric-id":1146524,"id":"Q1146524"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1070524$ECB88D86-4B84-4F34-BCE7-25F18EEE168C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"af8c032bdb108026ca1fd36470b08c87988e66ef","datavalue":{"value":{"entity-type":"item","numeric-id":5587568,"id":"Q5587568"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1070524$5B4954F5-6B9B-4A9B-A999-CEBBA9AFAB0F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8c10bb6d5ecfea92dae1751ce4566b8a283bfa86","datavalue":{"value":{"entity-type":"item","numeric-id":5546401,"id":"Q5546401"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1070524$A1332927-BE13-4EB9-89A6-F78A28F3DF76","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e7003e97c1ceb4c47469aaded8575bd9784cf852","datavalue":{"value":{"entity-type":"item","numeric-id":5660522,"id":"Q5660522"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1070524$E8DAD71A-C1E0-4D8D-ADBD-342FB6704838","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4eb8cc21703ca15dd783d9dceba1a9c26027bafe","datavalue":{"value":{"entity-type":"item","numeric-id":3922189,"id":"Q3922189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1070524$F249BD2B-ECC3-4EB1-9E7F-E2D297D545DB","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"31f44799e18fdb4266f7e1071400e20a78dbe9c1","datavalue":{"value":"https://doi.org/10.1007/bf01934510","type":"string"},"datatype":"url"},"type":"statement","id":"Q1070524$0F13CBF0-D930-4EBF-94F8-78459E859FD7","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"f786666d49eb1030043aecd0c56e90324439d1da","datavalue":{"value":"W1987048199","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1070524$91F54D15-0E99-4DC4-8828-B4C741226D8B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"df455ec9aceaa337a2eaa5db8897c48695098690","datavalue":{"value":{"entity-type":"item","numeric-id":919797,"id":"Q919797"},"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":"Q1070524$7B102B10-6BEF-4900-A832-5723C5168C45","rank":"normal"},{"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":"ac4420225e25a2c96650a95b8f11a231fd6a7849","datavalue":{"value":{"amount":"+0.8245160579681396","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":"Q1070524$089AD5AB-6733-4E53-8E97-F96E28DB57A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d1079e7e70057ae402ed5023d87a44a3de23d99a","datavalue":{"value":{"entity-type":"item","numeric-id":3499323,"id":"Q3499323"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2ae2815ea1aeceabd3eb4a663cba3f789b64f63b","datavalue":{"value":{"amount":"+0.8245158791542053","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":"Q1070524$740F8B34-EFE8-4711-83C6-DF87113F2DC7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3a413d3e72db275a1612f542f6301d7de4726ce4","datavalue":{"value":{"entity-type":"item","numeric-id":2242054,"id":"Q2242054"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ffd8608f6ce92e69a523179f31a2d758ba2b3ad4","datavalue":{"value":{"amount":"+0.823034405708313","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":"Q1070524$DBBEC065-F6EB-4A9E-A262-FF2D67D5CE1E","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":"e8c6748acf4ef38315beed5733b69da0471bd23b","datavalue":{"value":{"amount":"+0.8223199844360352","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":"Q1070524$1F5C1BB2-AF6C-4B2C-AC60-F14302918000","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Some performance tests of convex hull algorithms","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Some_performance_tests_of_convex_hull_algorithms"}}}}}