{"entities":{"Q876505":{"pageid":878353,"ns":120,"title":"Item:Q876505","lastrevid":65046699,"modified":"2026-04-11T23:57:48Z","type":"item","id":"Q876505","labels":{"en":{"language":"en","value":"Shortest monotone descent path problem in polyhedral terrain"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5144507"}},"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":"Q876505$866C93C7-F01B-46B5-BC26-9EF62AABD44D","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"acb1870a7788f6f527193cb51bbc6f0d6463e1b3","datavalue":{"value":{"text":"Shortest monotone descent path problem in polyhedral terrain","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q876505$0639C876-B9D4-4A15-B6DD-E6FA82BE49B8","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"0b1b5332922a34e58bc0db8e2a01431466be6468","datavalue":{"value":"1117.65037","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q876505$B581B23E-5298-46CF-B994-652348945323","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"e942506eb8a22329d6c664d17f1e74e5ee8a2415","datavalue":{"value":{"entity-type":"item","numeric-id":436690,"id":"Q436690"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q876505$ECA22ACB-786D-455B-BBB5-644F3AEDE0B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"8226b6fb1ff97895f08d961ea75f17a24dbb060d","datavalue":{"value":{"entity-type":"item","numeric-id":299088,"id":"Q299088"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q876505$E460F165-B44D-420F-A9E0-02A88E62BDB0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"fc7009695144800ec158194ab275c08a49785642","datavalue":{"value":{"entity-type":"item","numeric-id":407526,"id":"Q407526"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q876505$83D4EEDD-74A8-41E0-AAC2-9FE76CDF7F16","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":"Q876505$B0DC8ADD-3EF7-4635-A06E-469CFD1E9A8B","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"6f339c49c589764265da0f7de34a17b3e7a78e06","datavalue":{"value":{"time":"+2007-04-18T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q876505$848F3A0F-202A-43E8-AF9C-EC367CAAB809","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"1a125a073497b6013dc000a1de9122b31d51ef8c","datavalue":{"value":"Given a polyhedral terrain with \\(n\\) vertices, authors deal with the shortest monotone descent path problem. This problem consists in finding the shortest path between a pair of points, called source (s) and destination (t) such that the path is constrained to lie on the surface of the terrain, and for every pair of points \\(p=(x(p),y(p),z(p)),\\, q=(x(q),y(q),z(q))\\) on the path, if \\(dist(s,p)<dist(s,q)\\) then \\(z(p)\\geq z(q)\\), where \\(dist(s,p)\\) denotes the distance of \\(p\\) from \\(s\\) along the aforesaid path. The authors show that for some classes of polyhedral terrains, that the optimal path can be identified in polynomial time. For the general terrain the problem is still unsolved.","type":"string"},"datatype":"string"},"type":"statement","id":"Q876505$EF328736-D331-4B7E-B053-92EB603E354A","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"2ce72165d993b0b8ed97728d731d2db2473b9554","datavalue":{"value":"65D18","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q876505$2FAC6E20-A963-4298-A900-754DF21BB2C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"0b4fa5b59eb6fe6e43618f9e005f4a49f4390971","datavalue":{"value":"65K05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q876505$CDA0FBBD-D33E-43EC-A672-D36BCAA178A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"355ea56a4f84d7973d94c70a8b1f92966ec83542","datavalue":{"value":"65Y20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q876505$EEC80248-49AB-4B9E-9B01-8940D8D97A3A","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"91d32e78ac59c59210769bfd16ee1be1341d7d69","datavalue":{"value":"5144507","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q876505$4DD6DC5A-C9B9-4A14-810C-09534BEEA8CE","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"755e4d1db93cd2ed46b8f922d200ceac47b6f51a","datavalue":{"value":"polyhedral algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q876505$B48B9B57-3D88-4333-A84A-B6CF506B7901","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c5f8382ba04f9f05f645b4d0e4b9ea28f0619583","datavalue":{"value":"complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q876505$DBAED588-3B1B-41A1-BECE-750AD2E7BAAA","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"eabcaa4115c7d203cf999b1d6476a35edc125dbe","datavalue":{"value":{"entity-type":"item","numeric-id":256764,"id":"Q256764"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q876505$562797CF-713A-4FE9-AABC-C2E60866D4E5","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":"Q876505$CC195166-9B92-49ED-893C-62A4C70A6F9D","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"cf3296f8d9f86fd62cf828228a26306f0cb9868b","datavalue":{"value":"https://doi.org/10.1016/j.comgeo.2006.06.003","type":"string"},"datatype":"url"},"type":"statement","id":"Q876505$6712D1CC-4817-4460-847A-029FC6ED5D6B","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"598bf8dc74a17afc41b7c1b39c073889ebe9f4bd","datavalue":{"value":"W1974490777","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q876505$31C4FC3B-A635-4290-9A60-F0A8FF102D10","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"f915a62b0347f9bd9bb31f717f9a2d517416c892","datavalue":{"value":{"entity-type":"item","numeric-id":1601017,"id":"Q1601017"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q876505$8F2401FA-89A2-4526-B26F-38C81CC3B1F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"330b69d93d655e5d53f552dc222c3cd19b7c3e03","datavalue":{"value":{"entity-type":"item","numeric-id":3191995,"id":"Q3191995"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q876505$4267ED96-8DD9-4650-A6BE-8DC2499B3C0A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3aaf6dc4e29cec038dcf381dd9c0ab2bfaf170c5","datavalue":{"value":{"entity-type":"item","numeric-id":5900801,"id":"Q5900801"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q876505$596C3D52-6A90-4CC6-B2CB-4E1122A460FC","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":"Q876505$B49A1714-5105-4D4F-9B2C-FA61A978F7BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"72d76970364af7c1c73cd3be1fa54b43334ca800","datavalue":{"value":{"entity-type":"item","numeric-id":1361408,"id":"Q1361408"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q876505$72054AE9-D8AC-4C28-8C53-11B4C8088D90","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6fa0b997cfbf4b258512ab5be7c64381f9ab0f03","datavalue":{"value":{"entity-type":"item","numeric-id":4889502,"id":"Q4889502"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q876505$6D027182-77E9-4465-89CE-3FBA55897049","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"99114b1bd38a031039ee6a9bed0217048b0b5658","datavalue":{"value":{"entity-type":"item","numeric-id":1101224,"id":"Q1101224"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q876505$97F573BE-DC6E-42E8-8446-7CB28C82DFB7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"10a8acd3b84e5bd992c1bec057520941e4d6c016","datavalue":{"value":{"entity-type":"item","numeric-id":2819608,"id":"Q2819608"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q876505$3DDD39F9-37D8-434D-9E35-02E6C65A9173","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"03df246b4bf69f4b65dd2088c0666635fecc05ce","datavalue":{"value":{"entity-type":"item","numeric-id":1388131,"id":"Q1388131"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q876505$DA81B4A1-06CF-4735-AFC8-7907AC49DFFD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"813773fa16a57d5ba1f1f634d7f3bafad0c0476d","datavalue":{"value":{"entity-type":"item","numeric-id":3967063,"id":"Q3967063"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q876505$1EC524F6-55F6-45C8-A015-B977919DBC38","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"51846087153a1274fc18a736faceb627007db4b1","datavalue":{"value":{"entity-type":"item","numeric-id":5940611,"id":"Q5940611"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q876505$A82FA98A-D624-4F19-B48C-F06CE2F46DBC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0053466f05697a968a9e68654c037fc560cd32da","datavalue":{"value":{"entity-type":"item","numeric-id":3028357,"id":"Q3028357"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q876505$54BC9438-94F4-489B-A08D-7CB2D231F689","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":"Q876505$59B5576E-A57A-409D-857E-66D265AB1B0D","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":"Q876505$F89473A4-F2F3-4F52-B5DC-6E0A3AEC6720","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"028f912c941fdda16131fb2912cdd4b391b44bb7","datavalue":{"value":{"entity-type":"item","numeric-id":2749787,"id":"Q2749787"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q876505$C1A6D6C7-1259-4BCE-9322-331E764A98A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9b565804da2aed6b49ce97233f11bb7620901545","datavalue":{"value":{"entity-type":"item","numeric-id":5901265,"id":"Q5901265"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q876505$5DCA18BB-CEEA-4A2F-84F6-A833DA23EA7A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6d0747988e1676be65af03c5c1c4d58bacfb21f9","datavalue":{"value":{"entity-type":"item","numeric-id":4936005,"id":"Q4936005"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q876505$A39000E0-200F-4C0A-ABD1-5BFCF453F239","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"149a4fb7df2b438c04515073626756a2250a376a","datavalue":{"value":{"entity-type":"item","numeric-id":3753528,"id":"Q3753528"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q876505$81015907-A678-40D4-B17A-439E879A94E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8dc65328ad5528be88de5befa79d4146add6b970","datavalue":{"value":{"entity-type":"item","numeric-id":2706111,"id":"Q2706111"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q876505$CD3B3FFE-B3B5-435F-869F-D380547786D6","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"5cff96d075f3f5ab7a438d1b8fc85eb1d81eae5e","datavalue":{"value":"10.1016/J.COMGEO.2006.06.003","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q876505$BE71D2C5-D263-4470-AC2F-211B973BD0A0","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e1b1d86098b051a8eb0641651ac5981b89c42315","datavalue":{"value":{"entity-type":"item","numeric-id":5710682,"id":"Q5710682"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"740a84cef5eba4eb640033cc9c7c2efcaa3e9407","datavalue":{"value":{"amount":"+0.9654362201690674","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":"Q876505$547BC277-ADD9-4E33-AFE4-C91E1EABB3BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7e47ba61df5f7cc15d47c22d616bcc7654e10e4a","datavalue":{"value":{"entity-type":"item","numeric-id":1025303,"id":"Q1025303"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2cbd16b570910560905b5484c4ed5acc103bf857","datavalue":{"value":{"amount":"+0.8302164673805237","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":"Q876505$E85F1D3A-AF92-475C-B296-2884E8102D5F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"634b913439924a0d794fa0e700960e440fd0b376","datavalue":{"value":{"entity-type":"item","numeric-id":2434932,"id":"Q2434932"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b8e248cdfdc5fbdadafc8b8dfb4131b8417f0945","datavalue":{"value":{"amount":"+0.8289734125137329","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":"Q876505$9BBA58F6-6178-4200-B289-07B8B064B3AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"09b47c35df2094515f8037c86fc1a25ff74e64a7","datavalue":{"value":{"entity-type":"item","numeric-id":972363,"id":"Q972363"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ebc897615b76bf2d663784bf82710c5c5679059c","datavalue":{"value":{"amount":"+0.8100845217704773","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":"Q876505$B33C1096-E981-41FF-96D6-B696D691B41E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dd805a9661c571b7d156fb3deaf3c6173d115ea1","datavalue":{"value":{"entity-type":"item","numeric-id":3605485,"id":"Q3605485"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ef918351ad7cf8940b6c63e35bad489deadd56f1","datavalue":{"value":{"amount":"+0.8046685457229614","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":"Q876505$7C5AB0C5-FF4C-4B67-82B6-C685E33004DC","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Shortest monotone descent path problem in polyhedral terrain","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Shortest_monotone_descent_path_problem_in_polyhedral_terrain"}}}}}