{"entities":{"Q1104089":{"pageid":1114841,"ns":120,"title":"Item:Q1104089","lastrevid":42879273,"modified":"2025-07-15T16:06:02Z","type":"item","id":"Q1104089","labels":{"en":{"language":"en","value":"Parallel algorithms for shortest path problems in polygons"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4055044"}},"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":"Q1104089$A5522A6D-B966-4C67-966C-619CCB94675D","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"d9b15b0587e20e6fb744ce4a2fd992d16a715fac","datavalue":{"value":{"text":"Parallel algorithms for shortest path problems in polygons","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1104089$C61B1155-CED0-445B-8F79-4012FE7BE541","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"1843e1547aefc670b3314be3658b932142d92ba5","datavalue":{"value":"0646.68058","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1104089$C6BF77C0-35E5-44EB-BD0D-9FFC924E51D2","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"ec8dcec14c30f86e6ff9e8e8ed78edb1aa4951ce","datavalue":{"value":"10.1007/BF01901194","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1104089$24658251-4733-4AE3-B99D-22CB66ACC8F6","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"bb09e6fa86415c7b65f70686ba504edf3fca203b","datavalue":{"value":{"entity-type":"item","numeric-id":676649,"id":"Q676649"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104089$8DED8280-A6B6-42A3-85BF-EFA49B90D09F","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":"Q1104089$6F5A94E8-70D1-4871-86C7-4CC78DE08EC5","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"43813089db9b51ed7a23a6dbdbdac76a6962820f","datavalue":{"value":{"entity-type":"item","numeric-id":205026,"id":"Q205026"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104089$A973CBC5-57C7-4A8B-A743-02A1B419E3B0","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":"Q1104089$DECA20F2-23ED-4EFB-8DDC-D93F27E9A684","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"fab935319f27cfb92f5af1eb58f7ef0e41ba2ec5","datavalue":{"value":"Given an n-vertex simple polygon \\({\\mathfrak P}\\) we address the following problems: (i) find the shortest path between two points s and d inside \\({\\mathfrak P}\\), and (ii) compute the shortest-path tree between a single point s and each vertex of \\({\\mathfrak P}\\) (which implicitly represents all the shortest paths). We show how to solve the first problem in O(log n) time using O(n) processors, and the more general second problem in \\(O(\\log^ 2 n)\\) time using O(n) processors for any simple polygon \\({\\mathfrak P}\\). We assume the CREW RAM shared memory model of computation in which concurrent reads are allowed, but no two processors should attempt to simultaneously write in the same memory location. The algorithms are based on the divide-and-conquer paradigm and are quite different from the known sequential algorithms.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1104089$A7F941A6-E0C9-4E69-BB6C-4D47A5380550","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1104089$6C743AAE-6998-43A5-B31C-F61DA1810558","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1104089$DE792BDF-551D-4272-A93A-AA0ADA451C08","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e5762e9b09407c15760c5fa5cac71c82c32bf230","datavalue":{"value":"52A10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1104089$0155FF02-2729-48E5-A5C4-4EA5EA884C9E","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"f0f3755450c1018c682f5303b21cb125d46afbc1","datavalue":{"value":"4055044","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1104089$7D1861EF-4010-40FA-A12F-2F7A31A00BC9","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"551d108313cfab3a77b395a647aede7021169ebd","datavalue":{"value":"computational geometry","type":"string"},"datatype":"string"},"type":"statement","id":"Q1104089$52022DD9-5A3A-4720-83B9-2B37E55447CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d33669a46e6c8e8b36873d1f752821b7694a60c9","datavalue":{"value":"parallel algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1104089$F74AC2BE-8BBA-43BC-A176-C026DC679E9C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ed28385b5c62eaaf3b0756eb74715fae1afa8293","datavalue":{"value":"simple polygon","type":"string"},"datatype":"string"},"type":"statement","id":"Q1104089$84BC0476-F034-4002-AACF-99E47E8EEA40","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5f0ea58a0a54f75a3851c6c45fb33d0f1e9aa55d","datavalue":{"value":"shortest- path tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q1104089$55A08C59-66D6-4792-AB71-2D8747C2B594","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"741c7982a6e7a4729b35d2b94cd08a41085ad6f7","datavalue":{"value":"CREW RAM shared memory model of computation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1104089$E294D865-3250-4040-8FD5-563CED05F0EA","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":"Q1104089$816419A2-1A4B-4164-B7CA-8CC31A38D884","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"1b188894a982bcdcf44770fa94b41beb386059a7","datavalue":{"value":{"entity-type":"item","numeric-id":3942160,"id":"Q3942160"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104089$77C10CBF-0236-40FF-98E3-AB028D8BD844","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d2c6b273bbbfb23a71b64948d50760d60883087e","datavalue":{"value":{"entity-type":"item","numeric-id":1101226,"id":"Q1101226"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104089$586DBCBF-97A1-4A2A-840F-93119348BB4D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"085e1218a66243e307498d7e8b0c1d323937d638","datavalue":{"value":{"entity-type":"item","numeric-id":3337244,"id":"Q3337244"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104089$E3836B81-7284-46AB-ABF1-8F8E38B34F28","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":"Q1104089$A38F5CEA-F559-46E7-80D7-7B4F66578C29","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f51826f25d95525fd11a7363d44c95522afa1732","datavalue":{"value":{"entity-type":"item","numeric-id":3683547,"id":"Q3683547"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104089$ABD1D85B-60C9-4C56-B067-1CAAB8378A55","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"555ff90b1f1f9a6be840fb106d6702373b361344","datavalue":{"value":{"entity-type":"item","numeric-id":3309077,"id":"Q3309077"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104089$EDC8F66C-ED1A-4465-8310-14992743A076","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0c5477e08259683f4f1214eab272881c214067b5","datavalue":{"value":{"entity-type":"item","numeric-id":3694710,"id":"Q3694710"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104089$20C7A356-16E6-4B5A-8735-4D078D77CA37","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5ffec4d94b7b012095f39126ed96f3bf822347da","datavalue":{"value":{"entity-type":"item","numeric-id":1062764,"id":"Q1062764"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104089$394EA919-339A-46CF-AD7B-A4D527331D00","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"0216cd2458684d02e129e31545964996dbd7b400","datavalue":{"value":"https://doi.org/10.1007/bf01901194","type":"string"},"datatype":"url"},"type":"statement","id":"Q1104089$43325947-FDE4-4765-A303-51C47227ED4C","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"634ac4efd9ca8c1f464994594aede296ec457d91","datavalue":{"value":"W2052770190","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1104089$F0F83E70-80D8-4C9E-A159-9D1D211AA01C","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"45ee54ee93ae33dca72302fe06ae39e37b2a9888","datavalue":{"value":{"entity-type":"item","numeric-id":1201749,"id":"Q1201749"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"db4db426447df69fed5a7bd9b779530a19d4a37b","datavalue":{"value":{"amount":"+0.94993895","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1104089$B89A7200-F389-495A-8598-A52EEDB760D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"119138f87ce1a901c690480d19f587d0e995505d","datavalue":{"value":{"entity-type":"item","numeric-id":5056111,"id":"Q5056111"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"de2384369bbbdcd822e51cce841d00f22f3a349d","datavalue":{"value":{"amount":"+0.9314688","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1104089$D3FF3BB9-CF53-4DC9-A663-E17642EA7650","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"322c493ed0658d0b1d8482f898a30a3a3d8b4b42","datavalue":{"value":{"entity-type":"item","numeric-id":1187196,"id":"Q1187196"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7f53645961ec74aae2abb4af1ec4958d0ed47eda","datavalue":{"value":{"amount":"+0.9305513","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1104089$5DCC53CD-B824-4BE3-970E-447D5DB5D854","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"09501e241a64eb6112121d9e148f5b487750f6a9","datavalue":{"value":{"entity-type":"item","numeric-id":4511224,"id":"Q4511224"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"469bbf7fa655d2e91c30cf98c7a3ba0f4b598626","datavalue":{"value":{"amount":"+0.9280427","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1104089$851E23C6-FE7F-458A-A250-CCF328FB8702","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0f7d2bae9077c0302df7f2fb4aa3e19dbc27e4bb","datavalue":{"value":{"entity-type":"item","numeric-id":4005371,"id":"Q4005371"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d65c1f431f481dc2c4fb831dd33f93d994253559","datavalue":{"value":{"amount":"+0.9259873","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1104089$F38B83B2-549E-4B5D-8A6E-59345EF6DC70","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"15495f81f4974c1d9d887495cc2d67607af6d3d3","datavalue":{"value":{"entity-type":"item","numeric-id":1196454,"id":"Q1196454"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"10141cf21bf1ede9e181ecb1590919f1db0c017d","datavalue":{"value":{"amount":"+0.9245493","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1104089$FB1E3A14-D1C2-489A-B8F6-A85A53ECEB1D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2556a157741836329ceaad68a05ff40f66f6ea54","datavalue":{"value":{"entity-type":"item","numeric-id":2366233,"id":"Q2366233"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1e73912d64994474b187df81b21036721284c86a","datavalue":{"value":{"amount":"+0.9185044","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1104089$D1A99663-250B-47AF-943C-3FAA62F544FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f735feeee56aaf95a9f6f94b27057ef34eafd252","datavalue":{"value":{"entity-type":"item","numeric-id":5259593,"id":"Q5259593"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2970db07e687392e1e0b11bf0864d36afac4aa29","datavalue":{"value":{"amount":"+0.91781545","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1104089$ED82CFF1-67AA-4D28-9E41-70E798882E06","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"153fd4743b1dd132db2be482f56bca477fa146d2","datavalue":{"value":{"entity-type":"item","numeric-id":1112621,"id":"Q1112621"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6c7d3d9acb2ccaa91c5b96b755d29cec89c9b480","datavalue":{"value":{"amount":"+0.91768026","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1104089$D6A3C96A-1913-4B3B-A942-40D5D94A5B7E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1104089","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1104089"}}}}}