{"entities":{"Q2144452":{"pageid":2155195,"ns":120,"title":"Item:Q2144452","lastrevid":54339203,"modified":"2026-01-26T16:15:33Z","type":"item","id":"Q2144452","labels":{"en":{"language":"en","value":"An \\(\\Omega (n^d)\\) lower bound on the number of cell crossings for weighted shortest paths in \\(d\\)-dimensional polyhedral structures"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7541312"}},"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":"Q2144452$A1208FED-BAE7-4F99-9031-32911BAC5C8E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"5bac6344d14df053f020539f482636119c0315e9","datavalue":{"value":{"text":"An \\(\\Omega (n^d)\\) lower bound on the number of cell crossings for weighted shortest paths in \\(d\\)-dimensional polyhedral structures","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2144452$2C80AB0A-250E-4066-AF69-31290237467C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"7f1905ae101f9f94964765028be5ddaf56353088","datavalue":{"value":"1502.68300","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2144452$6570A0D7-8B0E-4F93-A7B3-05BC4F9A5F16","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"35dc49ec0939743c1f4eeb5dee14469ff17c7321","datavalue":{"value":{"entity-type":"item","numeric-id":1392201,"id":"Q1392201"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2144452$BD72712F-C996-4A15-818A-DB70F0447F6D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"38d792d47a26d779a5d4ebfefe81eefffc2d9963","datavalue":{"value":{"entity-type":"item","numeric-id":170448,"id":"Q170448"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2144452$84F28F18-4141-4D1C-918B-C4454E8798D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ca02099175697a4b54d6c3e10f20112dbf6ee98b","datavalue":{"value":{"entity-type":"item","numeric-id":170449,"id":"Q170449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2144452$A1029880-39EE-470E-A716-59D60A0DBE50","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":"Q2144452$85419A46-FC1F-45C3-88C1-975E6738F08E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"77075991782c40305711c3d33a7ecd0dd8eab84c","datavalue":{"value":{"time":"+2022-06-13T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2144452$4B30CE06-4642-49A1-85C7-D48F009835A7","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"0e9793942a59c67353f7953f7f9bd509649b826c","datavalue":{"value":"In the paper, the authors consider the \\(d\\)-dimensional weighted region shortest path problem. In this problem, we ask for finding the shortest path between two given points \\(s\\) and \\(t\\) in a \\(d\\)-dimensional polyhedral structure consisting of polyhedral cells having individual positive weights. They present lower bounds for the general \\(d\\)-dimensional case by constructing two novel \\(d\\)-dimensional polyhedral structures consisting of \\(\\mathcal{O}(n)\\) convex cells in which a weighted shortest path has \\(\\Omega(n^d)\\) cells crossings. The first polyhedral structure consists of a central cuboid and a set of satellite cuboids. The second structure consists of a central cuboid that is sliced, a set of shims (thin cuboids) and satellite cuboids.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2144452$74806F77-A746-4FD0-9E02-7B25666E2B58","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"159426a5937e62cfbbcc198dd4848ab52d6e715e","datavalue":{"value":"68U05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2144452$60F7AE28-3788-4C42-B1E0-40E36A79AA67","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2762df744fec88c5da60f696833f02907bd4417a","datavalue":{"value":"52B55","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2144452$565C6CDD-D2C2-4FA7-9557-0E66D0BE5378","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fd73672ce3d9f471e9d23297d964a3c571416abc","datavalue":{"value":"52B70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2144452$B661AB3F-0EFD-4879-B158-A29DD9881D51","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2144452$38DE8E2D-8DD0-4D4D-86C6-EFD918BCFD7B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2144452$59C4D740-FA1A-4B77-80AD-310961111EBC","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"573472946b59ff44deeb1b3a16a26945dab2eb67","datavalue":{"value":"7541312","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2144452$4D6210CB-3763-441C-8022-27EF185CE6DB","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"549ceeb00955b03ac073cc58bfe93ebd14850ed5","datavalue":{"value":"weighted shortest path","type":"string"},"datatype":"string"},"type":"statement","id":"Q2144452$BFEA219B-0DEC-4EAC-BB25-1ACD4B168AFA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f1f1814ebfb0c5873f215208cab188392d4def9a","datavalue":{"value":"lower bound","type":"string"},"datatype":"string"},"type":"statement","id":"Q2144452$D3302731-140C-4E40-8CAA-0AFD2197E1A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2ba0cc3f7aaac8445724ef309c9eecb57f5a563d","datavalue":{"value":"computational complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q2144452$B336B625-96F1-436E-8B94-AA40726F1ECC","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"4e8aff2b8e51ed9533d593cc755cbfae6f7c82e5","datavalue":{"value":{"entity-type":"item","numeric-id":305012,"id":"Q305012"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2144452$53291DF4-6509-4542-A473-9A4B2A6F983D","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"ce0f23a1450b88166e84d8a844a22644577f2bd2","datavalue":{"value":{"entity-type":"item","numeric-id":16271,"id":"Q16271"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2144452$34F7B26C-FAE7-468B-B6A1-D904EB77C021","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1463","hash":"e36a1e266e519ac45ce2f32f1219ad3192cb01ef","datavalue":{"value":{"entity-type":"item","numeric-id":18262,"id":"Q18262"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2144452$2C3A2E65-0D52-48C9-9F3C-13CBCE1E0C0E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1463","hash":"c5bf9d51a81fde970f73763c1b7d63013d05516a","datavalue":{"value":{"entity-type":"item","numeric-id":21213,"id":"Q21213"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2144452$0D65F4B3-61FA-45A0-901E-AB5DD4BFB081","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1463","hash":"aeeb0c85c3007a66879780eb682e442d7c043d34","datavalue":{"value":{"entity-type":"item","numeric-id":16234,"id":"Q16234"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2144452$2B5C2474-42FD-4D27-AB89-0902F8788B61","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1463","hash":"b08bc53a8f2b49982a67a5f7e680ef8258f21d76","datavalue":{"value":{"entity-type":"item","numeric-id":24702,"id":"Q24702"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2144452$A81E47AB-1481-4DB9-9F5B-6FE10FD8D42D","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":"Q2144452$43351CA8-FE20-4615-8D69-545E702C57F3","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"e8593ffc04772d40f70779d49dd18341dca5c765","datavalue":{"value":"https://doi.org/10.1016/j.comgeo.2022.101897","type":"string"},"datatype":"url"},"type":"statement","id":"Q2144452$0A6DC097-AC79-4D81-93CB-1C0A58A96A23","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"fc5a327163ca3e296d0ddfaa3ea1a15106125988","datavalue":{"value":"W4280652037","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2144452$6B119291-655F-4B5A-961C-304C508D1886","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"1ce8ee02d46c110212ca0f0242a45bec3cdeeb19","datavalue":{"value":"Q114195503","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2144452$893D51D6-0FA4-445D-ADCC-CD6D62AE69ED","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"6ca9379f173ea62405a63d8b10c34c823b41528f","datavalue":{"value":{"entity-type":"item","numeric-id":2081620,"id":"Q2081620"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2144452$96995B32-9CE7-43C7-915F-400091123E85","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2b989f45b85fa44137ad22092706b6102fd241bf","datavalue":{"value":{"entity-type":"item","numeric-id":78129,"id":"Q78129"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2144452$D64EC2E8-676E-45D5-9974-6D132D1D2278","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ab7ccab89225374454680d65f193383e61236777","datavalue":{"value":{"entity-type":"item","numeric-id":3020622,"id":"Q3020622"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2144452$4A12902B-D45A-4746-8C1A-9BBBD11190F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a8ada2e40bec2a038a8bd9915caf9b231a095216","datavalue":{"value":{"entity-type":"item","numeric-id":4302828,"id":"Q4302828"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2144452$E46E4219-9413-4838-93C1-89BE322A6AAD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a6e27bc34be41297a06ab186204bb95ab75e8b6e","datavalue":{"value":{"entity-type":"item","numeric-id":5361664,"id":"Q5361664"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2144452$5F24709A-692A-4CAE-92FC-CED3748C251D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"777a6eb43de90bea3ef727ccffab7f7c02686ee1","datavalue":{"value":{"entity-type":"item","numeric-id":2249044,"id":"Q2249044"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2144452$372A3B25-1E83-4EBF-B972-598A33D6FC8C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"50c365ae4f0f254a2f622f6d07b0f21ea0453b29","datavalue":{"value":{"entity-type":"item","numeric-id":3546286,"id":"Q3546286"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2144452$9BE2195B-0AEE-4D61-BC21-3308BA653644","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"de2fc23718b4c09929bb2d7f40be74625024a5f8","datavalue":{"value":{"entity-type":"item","numeric-id":5468868,"id":"Q5468868"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2144452$94816EF2-3D79-459A-B305-547B8228F5E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7c97142b118cf6405c8995b3adc2dd7601b6bbd4","datavalue":{"value":{"entity-type":"item","numeric-id":603866,"id":"Q603866"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2144452$AA8B733D-7008-469C-93A3-F178741155D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f24a05c764cbb6788e163f6052c871d03fc5c0ea","datavalue":{"value":{"entity-type":"item","numeric-id":5363017,"id":"Q5363017"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2144452$07A3FE64-4E81-426E-95C0-22D49817F635","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"791ce86f4bbae4a6b2333e39e5cb1fc55212df60","datavalue":{"value":{"entity-type":"item","numeric-id":2391841,"id":"Q2391841"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2144452$12055552-4985-4749-A855-63D305197D75","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"83c85b5f05cec03916f89261bd70eae0470034a8","datavalue":{"value":{"entity-type":"item","numeric-id":654287,"id":"Q654287"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2144452$F567A855-61C4-4C7F-A7E5-A299EF4E0613","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"136e3d2bc46b5ab698f18e5cadf870273b19eb6c","datavalue":{"value":{"entity-type":"item","numeric-id":5270714,"id":"Q5270714"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2144452$0E398682-A97D-4BC1-9A90-4867036E0E2B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"49f5fe16c10b367806254ac5d3ded4c8ea8c23ec","datavalue":{"value":{"entity-type":"item","numeric-id":4821338,"id":"Q4821338"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2144452$A5D9173B-398E-44AA-B582-ED29E9430AFC","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"29c6926ecd2c0475f70b605bf35f6955146beed5","datavalue":{"value":"10.1016/J.COMGEO.2022.101897","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2144452$B9DED787-0988-4A9F-AEC8-D3C463D7247D","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a07401a5233ccd31b447443315af7586e639058a","datavalue":{"value":{"entity-type":"item","numeric-id":2081620,"id":"Q2081620"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"170f0527e09a3e8861dd94e241cebd0eb4c19495","datavalue":{"value":{"amount":"+0.9202812910079956","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":"Q2144452$87B9B118-7EE0-482D-846D-44D321D03026","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"983718d9b88e16f1ec9e69e5135f8e91f42cf77b","datavalue":{"value":{"entity-type":"item","numeric-id":4302828,"id":"Q4302828"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"727ee9d81125d8629c58b8961aaeb8bf9a55fa90","datavalue":{"value":{"amount":"+0.7780985832214355","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":"Q2144452$A6EDD188-4152-4B11-B101-D7438AD9F068","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d715c650052ff6a997915e33b6efc1968053f79a","datavalue":{"value":{"entity-type":"item","numeric-id":3986396,"id":"Q3986396"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1599ce3eb61a592be07951f5f5e6dfb4661f3296","datavalue":{"value":{"amount":"+0.7759043574333191","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":"Q2144452$AEFCA762-7318-4D7D-AFAB-DD07B566D7D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"92c8a15c244f909ae5338598e9923ca84f2510b0","datavalue":{"value":{"entity-type":"item","numeric-id":3459847,"id":"Q3459847"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ee2764ae10b377f104984d6430b09010d1e546ac","datavalue":{"value":{"amount":"+0.772132396697998","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":"Q2144452$17D1AC0B-BFE2-4300-B0D6-BECE9C565EA0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"833bd09255d4ccedc4dbcf5ab54c87c10fc37d51","datavalue":{"value":{"entity-type":"item","numeric-id":5370569,"id":"Q5370569"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3a71b75d4d5c43343d4d1d8984dfbefc1bacaa5e","datavalue":{"value":{"amount":"+0.771008312702179","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":"Q2144452$86BD99EC-C8DA-4B04-A4DA-508B1210BF4A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2144452","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2144452"}}}}}