{"entities":{"Q2367127":{"pageid":2377870,"ns":120,"title":"Item:Q2367127","lastrevid":46347909,"modified":"2025-12-24T15:02:44Z","type":"item","id":"Q2367127","labels":{"en":{"language":"en","value":"An optimal parallel algorithm using exclusive read/writes for the rectilinear Voronoi diagram"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 232808"}},"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":"Q2367127$84E40E05-DE69-4E06-91A8-12439F9EEE4D","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"4510cdb265df7fd57da95ff193b0bd6c8820eee0","datavalue":{"value":{"text":"An optimal parallel algorithm using exclusive read/writes for the rectilinear Voronoi diagram","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2367127$5F2FF33E-445C-4501-AAFD-36317F247AA8","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"3ff79041af936efaf0ef5115d6832b4101cb0f38","datavalue":{"value":"0803.68132","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2367127$C36C9712-51C0-4DFD-8DB6-30AB5CE6B185","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"7ad51649d8654cc120ee43124861f50d7811c1e1","datavalue":{"value":"10.1016/0925-7721(93)90029-6","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2367127$5BFD91C0-13BB-4073-967A-2F71CAACA1ED","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"285beb29e5e30a7ba8792191178d7f52682884ef","datavalue":{"value":{"entity-type":"item","numeric-id":175378,"id":"Q175378"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2367127$75701D04-8739-4E87-A460-575DA2A27077","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"cac67b5af44da91dcbd20e8bc235f3b14eeda006","datavalue":{"value":{"time":"+1993-08-23T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2367127$F7F2B0B6-C0DB-4BE8-B462-EC12F90E97E1","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"7fc8f458ed1b9e4e0e8ebacce3281b7ff5bc0146","datavalue":{"value":"The paper presents a work-optimal \\(O(\\log^ 2 n)\\) time algorithm for computing the Voronoi diagram of \\(n\\) points in the \\(L_ 1\\) (or: Manhattan) metric, using \\(O(n/\\log n)\\) many processors and exclusive read/write only.   Such an algorithm was known before for the Euclidean metric in the concurrent read/exclusive write model.   The favourable properties of the \\(L_ 1\\) metric allow two linearly separated Voronoi diagrams to be merged in \\(O(\\log n)\\) time in the EREW model, using \\(O(n/\\log n)\\) many processors, by reduction to list ranking and prefix computation.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2367127$3DE6C0EF-804F-49CE-8D0B-217EBF181967","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"159426a5937e62cfbbcc198dd4848ab52d6e715e","datavalue":{"value":"68U05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2367127$D86FDDE0-CBB1-44C3-A975-932E29A36629","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b65efe51b183d0f4a672427b8171cd1e14211cba","datavalue":{"value":"68W15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2367127$9162EBA1-D311-4EBC-91D1-219BB1037D42","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2367127$0A1E6EF1-8E53-484A-B774-6A95D5D2ABE8","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d1b09980a386a677dfed9192ecde2f667fd2cb9b","datavalue":{"value":"232808","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2367127$12F852C6-2871-449B-9E89-DA932273C2EF","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"551d108313cfab3a77b395a647aede7021169ebd","datavalue":{"value":"computational geometry","type":"string"},"datatype":"string"},"type":"statement","id":"Q2367127$AB2199F2-E858-4481-A922-1F222C563697","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b995b9d468569d694c0cba480f8ef8954627bfbf","datavalue":{"value":"Manhattan metric","type":"string"},"datatype":"string"},"type":"statement","id":"Q2367127$54C5674F-662C-4DA3-BE69-6B16878326D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d33669a46e6c8e8b36873d1f752821b7694a60c9","datavalue":{"value":"parallel algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q2367127$572CDB99-C9CA-45B8-9B27-33F647F5A572","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d2a942004e7c3ebf174ed889f18fd8e1f8b9b24b","datavalue":{"value":"Voronoi diagrams","type":"string"},"datatype":"string"},"type":"statement","id":"Q2367127$B9D7C996-2C65-4C64-A1FE-EEFD508955CE","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"96c78da18b20f136727359e09ae1bfef8c52cfbf","datavalue":{"value":{"entity-type":"item","numeric-id":688448,"id":"Q688448"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2367127$5352FD24-C764-423A-9B42-34E7C5FF1D36","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"d10d7094195fd93795d0560abee20f8cd8844524","datavalue":{"value":{"entity-type":"item","numeric-id":166235,"id":"Q166235"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2367127$4FC65941-BDEA-45A3-AD1F-F0909DAD3206","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":"Q2367127$016D8EFD-55C0-46FA-8633-C38C04BA6D80","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"51739bff1c299c10033f47b5dbcd7cd23111a2c7","datavalue":{"value":"https://doi.org/10.1016/0925-7721(93)90029-6","type":"string"},"datatype":"url"},"type":"statement","id":"Q2367127$F7F96DF4-B2C9-4720-B15F-618CA0CC05E3","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"2f91ddd65163da391048ebceec5be09efe9b3b52","datavalue":{"value":"W2062586345","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2367127$6065ECAB-1033-488A-8F43-F6D1FB971CB1","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":"Q2367127$B83E9BA1-10A2-441C-9B93-472B3B15FAB8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0a19cf57099b1e6be1c56b1d816323c5aec82421","datavalue":{"value":{"entity-type":"item","numeric-id":3798228,"id":"Q3798228"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2367127$0AB39355-2292-46E3-9190-A5C7F37881D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"77348396ef7ced333be21b7a2a15cdf427712110","datavalue":{"value":{"entity-type":"item","numeric-id":3833633,"id":"Q3833633"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2367127$69089366-648A-4D4E-BBC5-78BED474D4AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a4077de5ad21c6b78a25ec43c56119974484a370","datavalue":{"value":{"entity-type":"item","numeric-id":4401551,"id":"Q4401551"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2367127$7CED929D-C1D3-4B5C-A463-AD4D21017D02","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f9cd35177b9fbbefa725a3537ebfd136511c156e","datavalue":{"value":{"entity-type":"item","numeric-id":1135110,"id":"Q1135110"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2367127$E32C764D-D240-43ED-B268-B9C0613027D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0c076610278811af0996195d1158f1ca302dd393","datavalue":{"value":{"entity-type":"item","numeric-id":4038709,"id":"Q4038709"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2367127$977C5AC5-78E9-40DC-88F6-4D3479E294CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c27205647ca572b79b66a603023449c3bc7df0f9","datavalue":{"value":{"entity-type":"item","numeric-id":582111,"id":"Q582111"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2367127$15E4DA62-5531-4BDD-A06C-77446E9203AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"29d0699d9da26d4080770c380efdeb17f5d5ec21","datavalue":{"value":{"entity-type":"item","numeric-id":4178506,"id":"Q4178506"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2367127$44F4475F-7778-465A-891F-A18C7490B35F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"18a470089a00352e63337f714a2fe06c97a8d9e9","datavalue":{"value":{"entity-type":"item","numeric-id":1825643,"id":"Q1825643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2367127$BCC8C09C-89AA-404C-87B9-FF68F65E11A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b2f422a6126daf14d9bc38a3327ee84be4512e26","datavalue":{"value":{"entity-type":"item","numeric-id":3890127,"id":"Q3890127"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2367127$A4BE1D4C-ED2B-408A-8FEE-B0FBA25C670A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"58d427a7be7364e105f0eb9a2691d3825b86ff8f","datavalue":{"value":{"entity-type":"item","numeric-id":3893362,"id":"Q3893362"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2367127$48A86384-0254-4062-AACB-24A6B02C6AE1","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":"Q2367127$1EA852DF-A6DE-41B7-B0AD-B4D7B54AAD5D","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2a84d7e73e2bec7b073e55a160843bc2df6ec972","datavalue":{"value":{"entity-type":"item","numeric-id":1123595,"id":"Q1123595"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f0c69f1ae5a23064359beedf8c3db0a1723f1e13","datavalue":{"value":{"amount":"+0.8367719650268555","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":"Q2367127$AD952408-D784-44C5-8272-8DDD75F078DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"198b5003824ac3af3293474f88eb2c2a519e6d94","datavalue":{"value":{"entity-type":"item","numeric-id":808303,"id":"Q808303"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d84e892c6613e062ef6ad9ac0df4c85e876c8654","datavalue":{"value":{"amount":"+0.8321713805198669","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":"Q2367127$E6C9CE05-16F4-4B4D-9D29-F59B2CFF3913","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d1b25e8fdeb539fde321fb55effd616bc9a8c380","datavalue":{"value":{"entity-type":"item","numeric-id":3796755,"id":"Q3796755"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b45388ee67bfd3f8a2cf28215d55825227520571","datavalue":{"value":{"amount":"+0.8303375840187073","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":"Q2367127$FA002D89-BC7B-4E3F-B2A4-E9C1DA82D64D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4fffc3167dc5962df5ece76127d5a5cb3a0b6abd","datavalue":{"value":{"entity-type":"item","numeric-id":5056167,"id":"Q5056167"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"05ca3835747f8bc94b0509452d85e6eed242a128","datavalue":{"value":{"amount":"+0.823249876499176","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":"Q2367127$81F327FC-F638-4FE9-A7D9-24FA0A5B5F46","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e6346566eb826f1274e388af11529ad0f5a97da6","datavalue":{"value":{"entity-type":"item","numeric-id":1269914,"id":"Q1269914"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b10604985da6e70efb6f46de41eae417198f49d4","datavalue":{"value":{"amount":"+0.809621274471283","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":"Q2367127$40225CBC-5932-4A02-BE9D-A5F95B89EDE8","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2367127","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2367127"}}}}}