{"entities":{"Q1823689":{"pageid":1834431,"ns":120,"title":"Item:Q1823689","lastrevid":43352468,"modified":"2025-07-25T01:05:14Z","type":"item","id":"Q1823689","labels":{"en":{"language":"en","value":"Optimal shortest path queries in a simple polygon"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4115970"}},"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":"Q1823689$2D086168-158E-4D89-A636-AA14ADEDFC3B","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"4d9786567763d8739d212f5c5583f06e5671f32e","datavalue":{"value":{"text":"Optimal shortest path queries in a simple polygon","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1823689$C1E33839-4146-4459-8E6F-3B13A196DB3B","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"274f40a4f198f54f6585e3271e0190a8ed3990d9","datavalue":{"value":"0681.68065","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1823689$F6118437-5EAC-42E7-B373-2069DEB49C88","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"dd2a547a4010b4ceabb3f720f486c6afafa9b3d1","datavalue":{"value":"10.1016/0022-0000(89)90041-X","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1823689$5D450B4D-1604-43F6-81D7-ADDD5AD1807A","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"27055c7a0af767b1f36b14e7674bc0aa2224fdc0","datavalue":{"value":{"entity-type":"item","numeric-id":534491,"id":"Q534491"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1823689$892A1BC9-2E61-44E1-8EB9-361D6F3FD302","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"94eab6fdb0a0437dc92c234ddacb5446e0f8992e","datavalue":{"value":{"entity-type":"item","numeric-id":1384195,"id":"Q1384195"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1823689$6B40F45E-B412-44FC-814B-97DBDB85E9E4","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"3340243f57e05f2265c56423c388055a14b114fa","datavalue":{"value":{"entity-type":"item","numeric-id":107189,"id":"Q107189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1823689$91D50996-2898-4437-9006-0B6BD03F12F7","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7211ad5ca16eb0d22cd0051fff3d0f3af254ceb6","datavalue":{"value":{"time":"+1989-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":"Q1823689$7ADC2938-2066-4DE0-9AF0-1DE844E84FDB","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"3c55141a5e7d15c8407a19a511f59e9be6ddb56b","datavalue":{"value":"The paper focuses on a simple version of the Euclidean shortest path problem: moving a point inside a simple polygon with n sides. It shows how to preprocess the polygon P so that, given two query points p and q inside the polygon, the Euclidean length of the shortest path inside P from p to q can be found in sublinear time 0(log n). The path itself must be polygonal. The paper gives a data structure that supports such shortest path queries when both endpoints are part of the query. The preprocessing phase gives a hierarchy of nested subpolygons over an underlying triangulation, such that any shortest path crosses a small number of subpolygons only. So preprocessing consists of triangulation plus a linear amount of additional work. Interesting applications and extensions are discussed at the end of the paper (disk moving, relative convex hulls).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1823689$61F7611C-C6C4-427B-A6F5-4DA09890E65F","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1823689$03651B6D-3027-45B4-B739-BC51C530E84F","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"70bbca3f694e4476f134f74c5533faa53ef86cb5","datavalue":{"value":"4115970","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1823689$21B36A08-1A8A-46BA-9D11-731181DF2F3D","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"551d108313cfab3a77b395a647aede7021169ebd","datavalue":{"value":"computational geometry","type":"string"},"datatype":"string"},"type":"statement","id":"Q1823689$F4DE46FA-DDEC-483F-AF55-49A08BD3314D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"596358b61297b80259e00b9995536e6529b13069","datavalue":{"value":"simple polygons","type":"string"},"datatype":"string"},"type":"statement","id":"Q1823689$D37BABC7-AD1E-411D-8461-9D91AB31D17D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4ddb05fb2558bbfe2b0cd87d3ae8cf91d8375600","datavalue":{"value":"shortest path moving","type":"string"},"datatype":"string"},"type":"statement","id":"Q1823689$84733A4C-CC67-45A8-8CD9-111F2C835A63","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"f97401dc38cdab90e116741461a88db9a2626407","datavalue":{"value":{"entity-type":"item","numeric-id":701798,"id":"Q701798"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1823689$41940796-3110-4B41-B394-9367F3EACB9B","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":"Q1823689$7A83A9C4-2DBE-4181-A1F0-ADE3BE9C1DF4","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"e78add1d8b013583dbc6de9c2424cecf91acefae","datavalue":{"value":{"entity-type":"item","numeric-id":1101223,"id":"Q1101223"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1823689$72887509-8B06-4965-88D5-6C02B0102B17","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e29b8e47936578f5cad24b50941e85f6a32ad9da","datavalue":{"value":{"entity-type":"item","numeric-id":3738618,"id":"Q3738618"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1823689$51E0ECC9-CC6A-4E72-800F-62EB551C48E8","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":"Q1823689$C9394F72-A794-482F-8E4A-D6F1DDA7CE33","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b0a715219fd6274692c890d4aa82ed20d1406419","datavalue":{"value":{"entity-type":"item","numeric-id":1158972,"id":"Q1158972"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1823689$1DDA2DB3-734D-415C-9E25-261B2386669E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ac6746c85a669097b515fb2d37dce6f94b8ec7c0","datavalue":{"value":{"entity-type":"item","numeric-id":3777450,"id":"Q3777450"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1823689$67CB52C3-A557-4DB2-89A1-071BEE51EF17","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"81cd7ab64c6ef61d8a257bd7a175f858125dd3a1","datavalue":{"value":"https://doi.org/10.1016/0022-0000(89)90041-x","type":"string"},"datatype":"url"},"type":"statement","id":"Q1823689$9C70ABAD-D7CB-4626-81DA-7727ED94A690","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"d8a41ad20543a3dc8bacbab78c26348469b1600b","datavalue":{"value":"W2038699153","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1823689$2A122FA4-8663-4E6E-8F9E-103AD7BCEB8B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5a436d6283113bcc7c86e4ac24f915917813efef","datavalue":{"value":{"entity-type":"item","numeric-id":4763413,"id":"Q4763413"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"df1d7cab2c14c7a8cc3c44a191ce105b525fd8f3","datavalue":{"value":{"amount":"+0.96113276","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":"Q1823689$AF3BA000-BE97-45F0-8C16-856A85F591B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0b938389ddb8afbef405bbfd7557f46245c31bb6","datavalue":{"value":{"entity-type":"item","numeric-id":3511429,"id":"Q3511429"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3f3a4504ce561bf45cfb54ab52555240e6e0f1d5","datavalue":{"value":{"amount":"+0.9582771","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":"Q1823689$2603147B-9C25-414A-B0ED-93219DE902D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1f45a450e2da07b9e4eca317cff0f0a4da275a3f","datavalue":{"value":{"entity-type":"item","numeric-id":4889507,"id":"Q4889507"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a71608aa156376016c3e10a53d0e270fe7427472","datavalue":{"value":{"amount":"+0.9479441","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":"Q1823689$579594AB-C01A-4F38-BC26-374B01406FF4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c8bd03dca9552f1679c2d764cde0f2bbdaf610d7","datavalue":{"value":{"entity-type":"item","numeric-id":2272388,"id":"Q2272388"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e27769f55ffea89b93b5e0ffe672a9440952b0b8","datavalue":{"value":{"amount":"+0.94689065","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":"Q1823689$EACBD4B1-0A4E-4726-9F2F-CDB7F10315FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"92f22cc640076ecd64364c55058419e561a23ad2","datavalue":{"value":{"entity-type":"item","numeric-id":1178232,"id":"Q1178232"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f00278f38b93795ab1d1aee7743fcaf099c3a4fd","datavalue":{"value":{"amount":"+0.941838","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":"Q1823689$1BC72CBE-4B25-4644-AAA0-04977A400FEC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b5ce9fa14f2692b21137e56adbb3c6aeefaaa40a","datavalue":{"value":{"entity-type":"item","numeric-id":3000734,"id":"Q3000734"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7c60c3c11d198c867c83a686c0a4fcd73f60910b","datavalue":{"value":{"amount":"+0.9265349","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":"Q1823689$BC6113A3-6FA0-4739-9108-02B52D3BF255","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9119efe0f0185c82452f6063e979141ffeb8a4f4","datavalue":{"value":{"entity-type":"item","numeric-id":4340963,"id":"Q4340963"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f1d72a2172df9ca1fcf0f2ba96bf89fb2bb12f51","datavalue":{"value":{"amount":"+0.92403704","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":"Q1823689$22E02ACD-866F-4D69-8C44-613774D8F4BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0b3f29eedf9c6baad70e98f1d30cc5ff89433d10","datavalue":{"value":{"entity-type":"item","numeric-id":2970464,"id":"Q2970464"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1e69ae43eda69d4d80339581ed2353d2fafec612","datavalue":{"value":{"amount":"+0.923828","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":"Q1823689$8A3BF24B-9B31-4520-B743-0FCA050A059D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c8f369f4c3c85418298a35f82e4632c25514fa84","datavalue":{"value":{"entity-type":"item","numeric-id":5368680,"id":"Q5368680"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1e69ae43eda69d4d80339581ed2353d2fafec612","datavalue":{"value":{"amount":"+0.923828","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":"Q1823689$85F8FF60-B0D0-41E6-91C5-1ECBFF6185E3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d30743ad3f43f4709daea073ffc9254e38aa8255","datavalue":{"value":{"entity-type":"item","numeric-id":2465622,"id":"Q2465622"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"27f6d94196edd2304e845ec9b9fea5b50e7b9e3e","datavalue":{"value":{"amount":"+0.91856575","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":"Q1823689$F6A62612-E794-43B2-903B-16FBBA02CC81","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1823689","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1823689"}}}}}