{"entities":{"Q1105374":{"pageid":1116123,"ns":120,"title":"Item:Q1105374","lastrevid":69653553,"modified":"2026-04-13T08:28:36Z","type":"item","id":"Q1105374","labels":{"en":{"language":"en","value":"Parallel algorithms for some functions of two convex polygons"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4058869"}},"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":"Q1105374$D4172D6F-2E90-4E02-B04B-CABE9478B14A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"9b162933701be9b041543124c4642072bc5adf7f","datavalue":{"value":{"text":"Parallel algorithms for some functions of two convex polygons","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1105374$80CFD4AA-4B44-4F84-8D60-6DD3F0DD8904","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"d04849aa591d9eeebb9aa706722cd976a0efa5f6","datavalue":{"value":"0648.68061","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1105374$46C2F1D3-87EB-4664-8CCD-62FB04C19DAA","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"0c82d3475e569239e0ac2c6430521bc66f65cdaa","datavalue":{"value":"10.1007/BF01762130","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1105374$F06916C5-818D-48F9-8AC9-450D11A089A2","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"54db673cbb28bd82524949973025fcdaf1d3af32","datavalue":{"value":{"entity-type":"item","numeric-id":522962,"id":"Q522962"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1105374$9CDE2D13-CCBE-463F-A7F3-460BAAF91ADF","rank":"normal"},{"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":"Q1105374$8DF4A451-704C-4A42-AC2B-02CF44FCEE88","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"65c8fa095fb5e7de7a6818fd747ab8b39647de93","datavalue":{"value":{"entity-type":"item","numeric-id":96582,"id":"Q96582"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1105374$1B268003-4B6C-4BB0-A462-AB82273A1F9C","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"31a1937240ca4a323604b4728c31d242b5596d7c","datavalue":{"value":{"time":"+1988-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":"Q1105374$5110B894-9487-4DAB-A491-2CF0038DCE3A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"a4648abda86299ef28b2118a12eaf4745d159845","datavalue":{"value":"Let P and Q be two convex, n-vertex polygons. We consider the problem of computing, in parallel, some functions of P and Q when P and Q are disjoint. The model of parallel computation we consider is the CREW-PRAM, i.e., it is the synchronous shared-memory model where concurrent reads are allowed but not two processors can simultaneously attempt to write in the same memory location (even if they are trying to write the same thing). We show that a CREW-PRAM having \\(n^{1/k}\\) processors can compute the following functions in \\(O(k^{1+\\epsilon})\\) time: (i) the common tangents between P and Q, and (ii) the distance between P and Q (and hence a straight line separating them). The positive constant \\(\\epsilon\\) can be made arbitrarily close to zero. Even with a linear number of processors, it was not previously known how to achieve constant time performance for computing these functions. The algorithm for problem (ii) is easily modified to detect the case of zero distance as well.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1105374$1B9303F0-C944-4062-81E9-9ED2F7B1FE77","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1105374$022BC8ED-590F-45D3-AB37-FCD89D70A059","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e5762e9b09407c15760c5fa5cac71c82c32bf230","datavalue":{"value":"52A10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1105374$B07FE7E1-578C-4CD7-89A1-3361DABB2059","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"3f63c91c4631bb60afc87b08cb94b4460492b575","datavalue":{"value":"4058869","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1105374$F788F2BE-547C-4650-8998-7203E448C04B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"551d108313cfab3a77b395a647aede7021169ebd","datavalue":{"value":"computational geometry","type":"string"},"datatype":"string"},"type":"statement","id":"Q1105374$6B284C54-9DAC-4C5A-B5FA-8C3E1EE1A87E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0fa312182bb7eaae3fd62e5da43ed90b053a6af4","datavalue":{"value":"convex polygons","type":"string"},"datatype":"string"},"type":"statement","id":"Q1105374$3E4BDFC3-1BE1-456D-BE4D-3C1E470302ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d33669a46e6c8e8b36873d1f752821b7694a60c9","datavalue":{"value":"parallel algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1105374$CFDC8907-2A8C-49C6-93BF-A18A225D92C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a8be2ffebbb202620011541831939d0e7ab17a89","datavalue":{"value":"model of parallel computation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1105374$C552E9D1-6D38-4194-8599-0C127F065126","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"706cbaf38c6b6f020af19f8912a2f5b05f76b998","datavalue":{"value":"CREW-PRAM","type":"string"},"datatype":"string"},"type":"statement","id":"Q1105374$DEA0544B-2410-4743-8369-9E1EAA7C3DF1","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":"Q1105374$B8D4A045-147F-46E9-9AFA-D116E7A50112","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"b307727eca196102f9e933ce115dc5006a0c0761","datavalue":{"value":{"entity-type":"item","numeric-id":1115600,"id":"Q1115600"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1105374$D29A596E-CC09-4E90-839B-27E653713149","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"618d5addc146aff60af5c68f98f5700e2a40a6c8","datavalue":{"value":{"entity-type":"item","numeric-id":3741079,"id":"Q3741079"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1105374$0F0F65A2-E370-4670-AE86-CBF4A4196E86","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":"Q1105374$030D55C4-9B22-4922-B881-76DCD2C31FC5","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":"Q1105374$4A19083B-9442-4FCA-8A29-AD9427232A66","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"694910451200ab7067ebbccacf142af3ac2a2369","datavalue":{"value":{"entity-type":"item","numeric-id":3992847,"id":"Q3992847"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1105374$603C7606-B58D-469B-B4E6-68F6C6139074","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"547131ab362814ee9a382fe7bef22e12f3b4f1f0","datavalue":{"value":{"entity-type":"item","numeric-id":4327390,"id":"Q4327390"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8c77035552a7f4032fdb7a88d3273871c5ed2465","datavalue":{"value":{"amount":"+0.8537377119064331","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":"Q1105374$3DF30841-0B58-4FF8-B29B-16D0B35F2FED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"180fe5ffbed2b9680ef6d17675b2b10ae4d70350","datavalue":{"value":{"entity-type":"item","numeric-id":3991698,"id":"Q3991698"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e22bfea1d824cfe80ca77c75afc598927cba3412","datavalue":{"value":{"amount":"+0.8517358899116516","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":"Q1105374$DF51E3D2-B6E8-4ECC-9FB8-49A2D3CA52C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a78be560ff1c1d0f083d0efd6936be0a6510ebc6","datavalue":{"value":{"entity-type":"item","numeric-id":685228,"id":"Q685228"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ae68df1f811b1b38506e09808c5fa3b892b489c2","datavalue":{"value":{"amount":"+0.8461427688598633","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":"Q1105374$C39F9E26-A6DC-41F3-8DBD-F35697C4DF38","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"691b85d54b55104c57619f63f6005bd081285e6f","datavalue":{"value":{"entity-type":"item","numeric-id":5289053,"id":"Q5289053"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9ef20bbd2d23d45c3058a1f31fe82e17ea1a05c9","datavalue":{"value":{"amount":"+0.8261606693267822","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":"Q1105374$762860E8-C5B9-44DC-A81D-DB37144F3740","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1116c07c8120baff4ea12fbe29a4d5ba8c9fdab6","datavalue":{"value":{"entity-type":"item","numeric-id":3787486,"id":"Q3787486"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"224a67157855a7dad948aa715f90dcd5a2bf2262","datavalue":{"value":{"amount":"+0.8142107129096985","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":"Q1105374$FC80AC3D-21FF-4B94-B6D9-0CC352FC90C3","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Parallel algorithms for some functions of two convex polygons","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Parallel_algorithms_for_some_functions_of_two_convex_polygons"}}}}}