{"entities":{"Q1085615":{"pageid":1096367,"ns":120,"title":"Item:Q1085615","lastrevid":49008478,"modified":"2026-01-06T11:31:46Z","type":"item","id":"Q1085615","labels":{"en":{"language":"en","value":"Shortest paths in the plane with convex polygonal obstacles"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3982536"}},"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":"Q1085615$2287FFC5-2F5E-49E8-880E-F25ED6D3FC62","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"bdd5960b06627fdb83723d2e37bb4a061dc2a636","datavalue":{"value":{"text":"Shortest paths in the plane with convex polygonal obstacles","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1085615$BF09DD0B-601F-4F79-8383-58B8D91F741E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"845c5422a063bc46ae9a00f086984299789b3b0f","datavalue":{"value":"0607.68052","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1085615$16036510-3D6C-4E19-B268-3841F95F538B","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"506ed6190089339cd78ab0e46e93ccdb2f9d10fe","datavalue":{"value":"10.1016/0020-0190(86)90045-1","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1085615$4440637A-2F4B-4EDD-9019-2B3EE7EC6529","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"89865038e9d6997e93e0e165725e57030439f915","datavalue":{"value":{"entity-type":"item","numeric-id":749236,"id":"Q749236"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1085615$B0231D3C-B64F-4003-8F8A-2BBD0BD654BF","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52fa7d44b58d0511cb8993765bd916aef86052d8","datavalue":{"value":{"entity-type":"item","numeric-id":63092,"id":"Q63092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1085615$482D9087-C237-4772-8159-20EE6064FBD4","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"63df7153432d81fa42019fcabb076c89649b0b5b","datavalue":{"value":{"time":"+1986-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":"Q1085615$25C9D024-492C-49AC-9B75-1B24B89E5191","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"107245dc59e6b03b1358af34d739f62a1dd7cd76","datavalue":{"value":"An algorithm is presented which computes shortest paths in the Euclidean plane that do not cross given obstacles. The set of obstacles is assumed to consist of f disjoint convex polygons with n vertices in total. After preprocessing time \\(O(n+f^ 2\\log n)\\), the shortest path between two arbitrary query points can be found in \\(O(f^ 2+n \\log n)\\) time. The space complexity is \\(O(n+f^ 2)\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1085615$1888D569-8085-425F-B76A-A82DA9BB15AB","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"25fe30a6fe5285f54b3a7ea7d7e97ac0b640e4f9","datavalue":{"value":"68R99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1085615$662B320E-8083-4E4D-A670-411CD14A1C70","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1085615$46713C71-2D26-413C-AA5D-D5775773B789","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"9dcf7939de5c9960e8e5b701952b339e8e08d57c","datavalue":{"value":"3982536","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1085615$46752478-48DB-4E48-97D7-8167EDDDCD23","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6b67103a36906f0730f73bab19b2cb5875f70908","datavalue":{"value":"convex polygonal obstacles","type":"string"},"datatype":"string"},"type":"statement","id":"Q1085615$5D10AF84-3CDF-4FF7-82B1-7B441E2BE9A5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"551d108313cfab3a77b395a647aede7021169ebd","datavalue":{"value":"computational geometry","type":"string"},"datatype":"string"},"type":"statement","id":"Q1085615$9EA65262-5ACC-44D0-9CBD-02F6BDB010B2","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":"Q1085615$DFD96709-38A6-4D43-A365-3F84C88BDCF9","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"485258cba783be9885c9488d0c9f019699425857","datavalue":{"value":"https://doi.org/10.1016/0020-0190(86)90045-1","type":"string"},"datatype":"url"},"type":"statement","id":"Q1085615$78FFC3ED-97F9-42F5-BF71-0BD07E37EC02","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"621ec45076078289cae62748e5739edcb35dc7f6","datavalue":{"value":"W2016584965","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1085615$BB5FCF10-47B9-48A0-B8AA-190D19F082C1","rank":"normal"}],"P223":[{"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":"Q1085615$8AB4F0E5-E82F-49DF-B02F-A82CD1BE00AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f09abd8d09729dc67252881c661ea2453195bec5","datavalue":{"value":{"entity-type":"item","numeric-id":3219753,"id":"Q3219753"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1085615$7ACE6CD8-CB23-4C32-A292-96A58625BC17","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0de7f01f97682395bcfb96932602f7ed7171bfb3","datavalue":{"value":{"entity-type":"item","numeric-id":1082820,"id":"Q1082820"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1085615$430B9A43-31A0-4CF8-97AE-D406A8FADDA3","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"932ab6c839a2d97fbcc33cb1606bf45bac566657","datavalue":{"value":{"entity-type":"item","numeric-id":1098634,"id":"Q1098634"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5cf761b2df72c187fbc69ffc66f72aae6d9ecbf8","datavalue":{"value":{"amount":"+0.9612906575202942","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":"Q1085615$0D78C978-36F4-4B0A-91D3-E7F38BA46A00","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2f774e8b4a69d635606ed04517ef79ce6592f5c4","datavalue":{"value":{"entity-type":"item","numeric-id":4323731,"id":"Q4323731"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a5a85b603711267bb583adffaabbb97fdd63e8df","datavalue":{"value":{"amount":"+0.9600660800933838","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":"Q1085615$A14E03A7-3683-42D3-A45C-BF987CDDE569","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"744867c08fba352614eca222a330107eb6a0a98e","datavalue":{"value":{"entity-type":"item","numeric-id":2957892,"id":"Q2957892"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a530d17bbc120b15a75d9217ba393a419469e754","datavalue":{"value":{"amount":"+0.9582781195640564","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":"Q1085615$4DA90DBA-05E6-4F2B-80DE-84C2DA788858","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4cb0a3dfd04a83240b51a570865a082f350732f4","datavalue":{"value":{"entity-type":"item","numeric-id":5687652,"id":"Q5687652"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"99ca49d6bccd7e6404df72255caa237d40ac466b","datavalue":{"value":{"amount":"+0.9355058670043944","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":"Q1085615$5AD5DA44-F4DA-464D-A93B-5DB7467E6909","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"934b18bec3e59a914236e0d90ba565cc50e101d4","datavalue":{"value":{"entity-type":"item","numeric-id":1380799,"id":"Q1380799"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0da32553f3841700004ab269858e22d458d2cd81","datavalue":{"value":{"amount":"+0.9140875339508056","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":"Q1085615$8B12FFC5-8271-4E10-BE37-96AB2BE65485","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1085615","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1085615"}}}}}