{"entities":{"Q312142":{"pageid":313909,"ns":120,"title":"Item:Q312142","lastrevid":56795550,"modified":"2026-03-23T15:19:22Z","type":"item","id":"Q312142","labels":{"en":{"language":"en","value":"Computing the Fr\u00e9chet distance with a retractable leash"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6627354"}},"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":"Q312142$EA5A81EA-1474-42C9-BAD1-2852A5D82C8D","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"5194b163aa24031f8d6d80eb32be463540206a92","datavalue":{"value":{"text":"Computing the Fr\u00e9chet distance with a retractable leash","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q312142$9A4BAD6A-663A-4DAE-9AAD-867160D451A3","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"45f967b570eb6402a3e3877540ccb125ffd358c9","datavalue":{"value":"1355.68277","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q312142$C25443C5-00C6-4A5E-8037-FB9CBAA7025D","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"d3a5290663200c60e3d3c8b72caf993a37ac18a7","datavalue":{"value":{"entity-type":"item","numeric-id":312137,"id":"Q312137"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q312142$51B92B3D-6D84-4ABE-B78A-6B8037D2D3E3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"69d51db80dda5f5249f89e3a96f8627e9753cd6c","datavalue":{"value":{"entity-type":"item","numeric-id":312138,"id":"Q312138"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q312142$F2C6B831-1606-4EEE-BDB3-08ECDCF4B8CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ba622ae16d906e92fdf535ecb13f33ada882f8ae","datavalue":{"value":{"entity-type":"item","numeric-id":312139,"id":"Q312139"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q312142$43C03A30-40A2-419F-A805-1C79E02EDDFB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"19837fcbff900d97aea78a8ba86804a24f0b8e2e","datavalue":{"value":{"entity-type":"item","numeric-id":312140,"id":"Q312140"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q312142$B012470F-D8CE-402F-88DA-12B7D82CE3E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"8402804d132105b21de1e92dcac2c27db3304a01","datavalue":{"value":{"entity-type":"item","numeric-id":312141,"id":"Q312141"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q312142$560769E2-8E92-4034-8DB3-2226D2480097","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"b6f367138a9ac2b85113cfed5a6fd5bedcc8944c","datavalue":{"value":{"entity-type":"item","numeric-id":178842,"id":"Q178842"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q312142$385A9EF7-FB19-4918-9BAE-7EDADE666E9E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"85729985fc5e9a7abe539dd204f756c75bb908ba","datavalue":{"value":{"time":"+2016-09-14T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q312142$75BF351F-3EDE-4AEA-BD8B-4E251306FF69","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"e841ce706f35ac03dda1d68279f897f7703d5b1f","datavalue":{"value":"https://arxiv.org/abs/1306.5527","type":"string"},"datatype":"url"},"type":"statement","id":"Q312142$1C91CC13-027D-43F8-BFC9-A31F60A82384","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"d20c541cdc82d39e1b3f581e702986c9dfd6d6e0","datavalue":{"value":"Let \\(P\\) and \\(Q\\) be two homothetic curves in \\(\\mathbb{R}^d\\). Given a metric on \\(\\mathbb{R}^d\\), the maximum of the distances between homothetic points of \\(P\\) and \\(Q\\) can be computed for every orientation-preserving homeomorphism that transforms \\(P\\) into \\(Q\\). The Fr\u00e9chet distance measures the similarity of \\(P\\) and \\(Q\\) by the infimum of such maxima. This paper improves the computation of the Fr\u00e9chet distance of two piecewise-linear curves with vertices \\(m\\) and \\(n\\), respectively, by using an original framework that does not rely on a decision problem. It takes quadratic time for polyhedral distances, and \\(O(mn(d+ \\log^2 m+\\log^2 n))\\) for the Euclidean case. Besides, a (\\(1+\\epsilon\\))-approximation under the Euclidean metric is deduced from the polyhedral distance implementation. It is conjectured that the approach could be useful in order to obtain a quadratic algorithm for the Euclidean case and as well as to improve the search of a homeomorphism that provides the Fr\u00e9chet distance.","type":"string"},"datatype":"string"},"type":"statement","id":"Q312142$E8E2F8C5-1DD0-46F2-8EDB-48E7B85E46C1","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"4a9845e651fdff2439458243efd6dd170f9040cc","datavalue":{"value":{"entity-type":"item","numeric-id":590531,"id":"Q590531"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q312142$0214D2A2-6917-4270-ABC8-CFD968422834","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"159426a5937e62cfbbcc198dd4848ab52d6e715e","datavalue":{"value":"68U05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q312142$ADB9B47F-DBE3-4494-B859-2059AE7C3EAD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a4228d21095b3348e9ea20aa0b63610107aad8cc","datavalue":{"value":"68W25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q312142$0932CBEF-B291-4620-A71A-F23FF4EDD67F","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8abf6313e42621697b4e0a7dc75933339799dfa0","datavalue":{"value":"6627354","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q312142$0168E37B-DA76-4630-992F-58D98DCA72C7","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"522ef134b45c200316fe02b79fefc6df71addcd9","datavalue":{"value":"Fr\u00e9chet distance","type":"string"},"datatype":"string"},"type":"statement","id":"Q312142$C055BA2D-BEA5-438A-BE37-A033B15409CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a734b85aa53b162aef5a378f979d7534388b20d2","datavalue":{"value":"polyhedral distances","type":"string"},"datatype":"string"},"type":"statement","id":"Q312142$E5A566BD-9596-4AAB-8C82-6D928F557BF4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d9127f5896104a114682d7836229c81d41f1e9fa","datavalue":{"value":"Euclidean distance","type":"string"},"datatype":"string"},"type":"statement","id":"Q312142$D6B4BECA-EA77-445D-8BC0-091B6D67CB9A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dc058f54aac0023b7543c366366b86bc4e72c56b","datavalue":{"value":"approximation","type":"string"},"datatype":"string"},"type":"statement","id":"Q312142$FA6CFDD6-B4D3-43A1-99EF-53CFA6C36C16","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":"Q312142$108874D1-6746-4B31-8870-CD2C7A3CE3AC","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"71ec4230ff159b57b41f5132d48f2872fc2f8921","datavalue":{"value":"W2122538444","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q312142$ADCE52CE-FC8A-41BE-8E13-A268C4586D13","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"7a61d99be6ea6a854eeb95b5b682d88348192a71","datavalue":{"value":"Q59469027","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q312142$F8D834F5-806C-4E69-8399-C52C4E46A766","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"e94be88ba66e8de3ee43ec36495806a1f5f49609","datavalue":{"value":{"entity-type":"item","numeric-id":4698353,"id":"Q4698353"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q312142$9642B4F4-3312-40C6-B31E-E937BD4BD073","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"587826eeeb4ef9413dbf68e58e5e39b0583c5435","datavalue":{"value":{"entity-type":"item","numeric-id":2762787,"id":"Q2762787"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q312142$4A32A12C-53DF-4BE0-839F-B34008D3174D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5cf2f720939b370af6428f1b233109e3ec97f03e","datavalue":{"value":{"entity-type":"item","numeric-id":2970465,"id":"Q2970465"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q312142$68FE54C2-0EE9-4530-B69E-50A9CCB4A275","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":"Q312142$8621C875-BC01-4A0C-9AA3-395882BF0D0E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6852ec805a83b4812a204b17797fdd8e069ca6f9","datavalue":{"value":{"entity-type":"item","numeric-id":2721968,"id":"Q2721968"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q312142$E5658069-35E6-4B15-982C-0B1902A24BEC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c7b593e01b86dfe75876fea772f62bd643e38b4e","datavalue":{"value":{"entity-type":"item","numeric-id":3089091,"id":"Q3089091"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q312142$97E4B2B7-57F9-4D7F-AF4E-2DDAA055077C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1312825f2ea1c909da14a67a8d6b0d55b1c8962d","datavalue":{"value":{"entity-type":"item","numeric-id":5384065,"id":"Q5384065"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q312142$86C69876-8C3E-422E-8B1F-F61919B7E620","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a0e35387a231f0c89043d382fba7d0d98bda9108","datavalue":{"value":{"entity-type":"item","numeric-id":3188991,"id":"Q3188991"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q312142$107777B5-0B40-4389-AAC8-CABE8AEE214D","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":"Q312142$DD210B22-93C2-4371-BF31-C9CC1D020E83","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"13476d0caaf19ce40d7440b8c291535567e07106","datavalue":{"value":{"entity-type":"item","numeric-id":443909,"id":"Q443909"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q312142$FAC34C3A-8BCA-4E0E-B2C5-9F420437D0E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d83102276628748c7892331bdeada80ac25b5242","datavalue":{"value":{"entity-type":"item","numeric-id":2768388,"id":"Q2768388"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q312142$E1299E4D-DCEC-4E77-9546-6B7049EC6E13","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"a5e4a991fff6146e8635bba62f270949b8f43df2","datavalue":{"value":"10.1007/S00454-016-9800-8","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q312142$BA0A7BB7-B737-46EA-A44A-198F752D2357","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"de8401bae2cadc072632f7dcd5ca3ea474a4b0b5","datavalue":{"value":{"entity-type":"item","numeric-id":2849314,"id":"Q2849314"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bbab897a6d3e720dc80b67e0eef4e13e205a07dd","datavalue":{"value":{"amount":"+0.9999999","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":"Q312142$FAB0827F-597D-4690-A90D-A8976B15714B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2eaeb8291ff79cbcd4ee1e5e7ad9e2b7f5cb5f34","datavalue":{"value":{"entity-type":"item","numeric-id":5396948,"id":"Q5396948"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7fb28f68a0ff5c75b6cdb229755cb9820ff85e48","datavalue":{"value":{"amount":"+0.8421903","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":"Q312142$04350AA8-E221-4853-8310-2622B605101A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e313c4c70a57569148d0c045f40206d629acd22a","datavalue":{"value":{"entity-type":"item","numeric-id":5743403,"id":"Q5743403"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7a06526613678dca6c56747ead59a2f72cb4c664","datavalue":{"value":{"amount":"+0.84219015","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":"Q312142$34BC471C-F5B1-4DF2-AFB7-CDA834EF0AE8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2b279ecb2151f3d7f0e696acb6dff9acf7f70459","datavalue":{"value":{"entity-type":"item","numeric-id":2022625,"id":"Q2022625"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b3d270d41b3fc81494554b2dd57a91a643e830a6","datavalue":{"value":{"amount":"+0.83075273","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":"Q312142$BCF29AFA-E257-47DE-B806-9102FF279E92","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0007703f80d81716ee4c9186f490afa43295b047","datavalue":{"value":{"entity-type":"item","numeric-id":4580117,"id":"Q4580117"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7dcc2006a3b87dad358ffbe89cf8a58c9a05f5b5","datavalue":{"value":{"amount":"+0.8307526","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":"Q312142$85AAD092-BCE4-400B-B0FF-D4B425941C95","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8ec1fc4d0668c3de4cb0bd9033172d57b0bd63d1","datavalue":{"value":{"entity-type":"item","numeric-id":5088944,"id":"Q5088944"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"be7d5d8f1400c30f92b24b98f9054885a965efc2","datavalue":{"value":{"amount":"+0.81976485","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":"Q312142$EB8C47D8-2311-480E-8DD6-90E38DD66C30","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e69e9ffb760009d12f962a739048e820f64e7ccc","datavalue":{"value":{"entity-type":"item","numeric-id":4958385,"id":"Q4958385"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"64bab2e08310bb3e96a96c4deebe49a8b7da6df0","datavalue":{"value":{"amount":"+0.8197648","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":"Q312142$64FA09F8-8E75-4955-97D7-F6E078395136","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"77aab02279ab94a7cc492f40379f934f3243df17","datavalue":{"value":{"entity-type":"item","numeric-id":4698353,"id":"Q4698353"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b79b262d1017b94acb121ddf861f4d9b83ca57fa","datavalue":{"value":{"amount":"+0.813051","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":"Q312142$79BADC06-10C8-410E-83AA-ACD331FC0BCD","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"45fcd4163b5f33e6e8c784f5522d7246c0a1a61e","datavalue":{"value":{"entity-type":"item","numeric-id":57056,"id":"Q57056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q312142$06D31FD1-4CA9-406A-A18B-7A180840823B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:312142","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:312142"}}}}}