{"entities":{"Q1108791":{"pageid":1119540,"ns":120,"title":"Item:Q1108791","lastrevid":66734892,"modified":"2026-04-12T12:30:58Z","type":"item","id":"Q1108791","labels":{"en":{"language":"en","value":"Finding the convex hull of a sorted point set in parallel"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4068277"}},"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":"Q1108791$363BA454-4A82-460B-9127-D1A3FBAA87CF","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"12da180fa7beb0450eb68f9c5665aa9765818791","datavalue":{"value":{"text":"Finding the convex hull of a sorted point set in parallel","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1108791$3B30E11B-E811-48B5-A9C2-242DC681452B","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ae52d65690751aafc7d4cd520c4a3fe99c246436","datavalue":{"value":"0654.68047","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108791$D2C9742C-1FB2-485E-B1DF-D32BA8963424","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"06e0d576e0ada7af15e8391799d51ecb2b0f6288","datavalue":{"value":"10.1016/0020-0190(87)90002-0","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108791$4CA365BA-7A6F-4899-BD8E-4791A88BCCC1","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"d767c44768753f776586f48d5e20a1eeed0afa26","datavalue":{"value":{"entity-type":"item","numeric-id":378240,"id":"Q378240"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108791$04C18B08-F3CA-41FE-82D5-3DBCE2F0544C","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52fa7d44b58d0511cb8993765bd916aef86052d8","datavalue":{"value":{"entity-type":"item","numeric-id":63092,"id":"Q63092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108791$8D736A1F-FFED-47AC-934D-603D27613231","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5ae48c61eed19d1e1e1f33f9255d5b329362d064","datavalue":{"value":{"time":"+1987-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":"Q1108791$6FFD9D1E-42EF-4A22-A860-E01B35D822B6","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"b2bc792cca1c848e2220c5e8b9f66e265345607e","datavalue":{"value":"https://docs.lib.purdue.edu/cstech/567","type":"string"},"datatype":"url"},"type":"statement","id":"Q1108791$6CA357E6-8987-4E53-B81D-A1EE79EC2063","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"cc5da7bb16870f2064db27ad12bc55aeb08a1aa6","datavalue":{"value":"We present a parallel algorithm for finding the convex hull of a sorted planar point set. Our algorithm runs in O(log n) time using O(n/log n) processors in the CREW PRAM computational model, which is optimal. One of the techniques we use to achieve these optimal bounds is the use of a parallel data structure which we call the hull tree.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1108791$0BBBB685-4E9D-4B4C-9BE3-6E49D6B9276F","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108791$E51378CE-7EC5-47FB-84EB-7AE725145715","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e5762e9b09407c15760c5fa5cac71c82c32bf230","datavalue":{"value":"52A10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108791$EECFFFA4-8C6E-4360-9CFF-B02E14B33F5F","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"da5c14ce5cf2bae417016c0c25b686fd2d7132b3","datavalue":{"value":"4068277","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108791$A2122240-AFE0-45CB-954A-36795738447D","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"551d108313cfab3a77b395a647aede7021169ebd","datavalue":{"value":"computational geometry","type":"string"},"datatype":"string"},"type":"statement","id":"Q1108791$9F7BF0C0-9DDB-45F4-9E87-789DFE95B3BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7524eff3be377b3373bf1ae15aa61fe821e44b35","datavalue":{"value":"divide-and-conquer","type":"string"},"datatype":"string"},"type":"statement","id":"Q1108791$26AE2265-6AE8-4CA8-9019-D5FB496B7488","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0967c5f93d36d6aa18ee008d77ee288965d952b9","datavalue":{"value":"parallel algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1108791$356D9F7C-90A2-4C92-8B6E-B990B2C09F5C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"697626a6c5ea4a7921eba4e0f3fdba17e2e290d9","datavalue":{"value":"convex hull","type":"string"},"datatype":"string"},"type":"statement","id":"Q1108791$24C029EB-2378-4668-8146-2D59DB5E5378","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"34f1528cd9548b088936bf54fdf77b3eb118e9bc","datavalue":{"value":"CREW PRAM","type":"string"},"datatype":"string"},"type":"statement","id":"Q1108791$451CF18A-07CD-4DFF-8AAD-561F297BE98E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"834234169d46b8b869f328d05b87d377eb5a764d","datavalue":{"value":"parallel data structure","type":"string"},"datatype":"string"},"type":"statement","id":"Q1108791$79F8BF9F-F2AA-487B-BD36-D98052E766CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e630a02c8dc017a02802535f2bc2d8e15757f3e0","datavalue":{"value":"hull tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q1108791$4692A93C-9A71-43D0-9891-30796FEAD69E","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":"Q1108791$8394672F-3A45-42ED-80D5-EC8DC3BAC55B","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"0e7e47283f91a26a75b32252d217e1bf248778a6","datavalue":{"value":"W2016482138","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108791$F140F259-9BE9-4C4F-96A2-9489B4D8B47D","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"fa83e54ac0960c38a34a164c9912c5330eee215f","datavalue":{"value":{"entity-type":"item","numeric-id":1906048,"id":"Q1906048"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108791$D0568B39-313C-4FA0-A137-609FA3F48593","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":"Q1108791$082A7E86-B887-4B49-9D4D-39C3008FB3CC","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":"Q1108791$C9F87210-2C93-473A-A195-F4724BD399D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"508894c78bd2770d073dbe57a0316a7e71f6bc30","datavalue":{"value":{"entity-type":"item","numeric-id":3890136,"id":"Q3890136"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108791$34FE015D-0385-4C8B-9E2A-532FA769E92C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b0a715219fd6274692c890d4aa82ed20d1406419","datavalue":{"value":{"entity-type":"item","numeric-id":1158972,"id":"Q1158972"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108791$8DF98F04-F77D-4F0F-9F1F-09B79FAB1154","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"29f27c636d822aedfcb621168990c2025be43100","datavalue":{"value":{"entity-type":"item","numeric-id":4190154,"id":"Q4190154"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108791$40E68B00-E918-4972-8690-6D191146D86F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f62acb5eac89db2e3c6032dabab2d88e9279dd27","datavalue":{"value":{"entity-type":"item","numeric-id":4110607,"id":"Q4110607"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108791$95E6D3DE-70EC-4AB0-B0F7-24C02F7782B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"043dcc0f29f53940bfba3ed1768bc10874bfa632","datavalue":{"value":{"entity-type":"item","numeric-id":1260355,"id":"Q1260355"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108791$A178E2ED-665E-4C6D-A93C-C705D4C55A96","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":"Q1108791$046B6B46-C86D-412F-9F5A-E407E4561743","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a7ee4649f95b0c25c89a86d79800991243d452c0","datavalue":{"value":{"entity-type":"item","numeric-id":4889509,"id":"Q4889509"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"568ef1fe149d80c9128a90b9eba67b38c406aaea","datavalue":{"value":{"amount":"+0.9493094086647034","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":"Q1108791$55734DB2-B8CF-4EAD-BDF2-167831EF4DCC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7f1e694f2c30556d76520ac9ae392d2d1c73e5b2","datavalue":{"value":{"entity-type":"item","numeric-id":911280,"id":"Q911280"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9d456c2274e3add18e8838d626a0374209389801","datavalue":{"value":{"amount":"+0.9221240282058716","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":"Q1108791$431A5FA0-7769-41E7-84EE-DE6C0FF0FFB3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b8c02dcc42f5451d80cbdbe9e97a96be52c3bc6d","datavalue":{"value":{"entity-type":"item","numeric-id":3814810,"id":"Q3814810"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ec8c96bfbf2f7d09c07040a9e1e31045eca73000","datavalue":{"value":{"amount":"+0.8953949213027954","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":"Q1108791$653CCF8D-4C1F-4998-8931-DF9DCF2DFE7C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4c8924bac787d35466f96a0462d01ab90262cc69","datavalue":{"value":{"entity-type":"item","numeric-id":676065,"id":"Q676065"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2c7ed733a283df19a3ca635ebf568c4414d02c89","datavalue":{"value":{"amount":"+0.8806222677230835","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":"Q1108791$FE104A07-76F0-4044-B2B2-64F3984C3D6B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bfe1f0efde9622f9f19b7e6b6b247741138eb401","datavalue":{"value":{"entity-type":"item","numeric-id":1899449,"id":"Q1899449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d8df315d0e1262e09d8417791de091bdf58f0196","datavalue":{"value":{"amount":"+0.8624179363250732","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":"Q1108791$591F57F9-FA51-45A6-B5D7-DFBAC8416521","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Finding the convex hull of a sorted point set in parallel","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Finding_the_convex_hull_of_a_sorted_point_set_in_parallel"}}}}}