{"entities":{"Q1869745":{"pageid":1880487,"ns":120,"title":"Item:Q1869745","lastrevid":48088972,"modified":"2026-01-03T14:38:06Z","type":"item","id":"Q1869745","labels":{"en":{"language":"en","value":"Approximate congruence in nearly linear time"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1902834"}},"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":"Q1869745$9990C565-BB24-46EE-938E-3C08AF88DC69","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"7dd3296108751cfa2f08ea926792c2271a0dd40d","datavalue":{"value":{"text":"Approximate congruence in nearly linear time","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1869745$797A925A-32A1-47D8-94A5-E5EA1220C55E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"56d61ed42331adeae678e80969978e9f39654e98","datavalue":{"value":"1018.65025","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1869745$A36DCBAB-9EA6-4694-A625-61DD0C9274ED","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"20416bd2963f7511dab633919e405d502f1e73e6","datavalue":{"value":"10.1016/S0925-7721(02)00095-0","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1869745$25EAC1EF-3230-4051-92EB-729BD081CFA4","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"b7931955f1f617c7544e605edee3db1fe0846e3b","datavalue":{"value":{"entity-type":"item","numeric-id":732030,"id":"Q732030"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1869745$14CDA9AB-FD8F-49B7-9500-A671384F3FFB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"907a1e2024ad69f38d5e91bb5007ab379bcf5c77","datavalue":{"value":{"entity-type":"item","numeric-id":1762984,"id":"Q1762984"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1869745$158F20AF-E749-4E75-B69A-1C5255B3A68D","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":"Q1869745$A719C08A-BD8E-49DF-8A38-06359727D759","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3b05751a28df8b7d171e02c18dec5082d33efa41","datavalue":{"value":{"time":"+2003-04-28T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1869745$806FE8F7-9082-4D85-948B-34158A874484","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"dbd57f9532a93832804692d7e6f7ab3ce90dfad8","datavalue":{"value":"Generalized bottleneck distance is defined as a point set distance measure that includes as special cases the bottleneck distance and the Hausdorff distance. The new formulation allows to achieve a tradeoff between the quality of match (guarantees that only a few points are mapped to any point) and the complexity of the matching procedures (near-linear time approximation schemes for minimizing the distance between two point sets in the plane under isometries). The results are based on the reduction of the geometric matching to combinatorial pattern matching. Supplementary, it is obtained a combinatorial bound on the metric entropy of certain families of geometric objects.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1869745$0E776C57-0635-4A91-BD94-4F78A18FF33F","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"2ce72165d993b0b8ed97728d731d2db2473b9554","datavalue":{"value":"65D18","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1869745$D527A8D4-FFED-4BC3-B0E3-81E6906440FF","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"9893903ba51921b84552530e043e3a942706c836","datavalue":{"value":"1902834","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1869745$F7E0F189-2157-4D1B-9D9C-1325A6D9DB65","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"551d108313cfab3a77b395a647aede7021169ebd","datavalue":{"value":"computational geometry","type":"string"},"datatype":"string"},"type":"statement","id":"Q1869745$C2B310D3-615E-43A3-A594-F152167F40DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8c7b8eb72751a0fef88ab139aad3223ad8293587","datavalue":{"value":"bottleneck distance","type":"string"},"datatype":"string"},"type":"statement","id":"Q1869745$E25C5288-5729-4FC4-BFCD-EF25835EA488","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2450e02f50939b46b52c3140c8d1d485cebe36e5","datavalue":{"value":"pattern matching","type":"string"},"datatype":"string"},"type":"statement","id":"Q1869745$E382DD54-BB3E-444D-BB51-55294BACFCEB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"de724f57f2ca30562fecbd99ea7381b6673771f1","datavalue":{"value":"Hausdorff distance","type":"string"},"datatype":"string"},"type":"statement","id":"Q1869745$EBDDD974-651B-4F82-920A-CDB1D9136898","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"87d7e2d6162851b4dd3f1f509ee3fc25d188458f","datavalue":{"value":"geometric matching","type":"string"},"datatype":"string"},"type":"statement","id":"Q1869745$6DED3BDB-2FCE-4419-A64A-AE96145B0AFE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"eb969966e4f8d0cc212fac9b8658484e2b07726c","datavalue":{"value":"combinatorial pattern matching","type":"string"},"datatype":"string"},"type":"statement","id":"Q1869745$11E7438B-85EA-48D6-B581-F713C698043B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7887e5db0d5f1573204e5ffd612e079d69a813de","datavalue":{"value":"metric entropy","type":"string"},"datatype":"string"},"type":"statement","id":"Q1869745$65DD019F-CF87-4633-BE74-15D0348AAEC8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bef81487c235fb93960d3747a1ea458873239384","datavalue":{"value":"geometric objects","type":"string"},"datatype":"string"},"type":"statement","id":"Q1869745$F60578AE-6C43-4BF9-9B98-178A9E6983DF","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"2f9e16b52bc8c390b9fea0fb31de1975133dd070","datavalue":{"value":{"entity-type":"item","numeric-id":455938,"id":"Q455938"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1869745$D5D8D029-888E-478D-82DB-9D5D15921E8E","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":"Q1869745$34E3A009-B11D-42A3-8384-5B754E04AB11","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"1d2b12d47c70d4fbf01f35882d9c1e29d5f7e677","datavalue":{"value":{"entity-type":"item","numeric-id":4945503,"id":"Q4945503"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1869745$1259627F-7B9D-4709-A06B-C67A4F2538C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5ce2ef55371a99d6397bb516f4b6460397b20664","datavalue":{"value":{"entity-type":"item","numeric-id":1822962,"id":"Q1822962"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1869745$2807AA36-9DC6-441D-A467-FF9813418839","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"beb271069ea5cfd0a1a8d3a41cf46bbae66ea224","datavalue":{"value":{"entity-type":"item","numeric-id":1891128,"id":"Q1891128"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1869745$F514E542-0E08-4D07-BA6B-4121CEF51F33","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"96f101d083d0a14f8ead99b615e35447a71b7026","datavalue":{"value":{"entity-type":"item","numeric-id":4024310,"id":"Q4024310"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1869745$667B0BFD-E84D-4B24-BAE2-8A1EE2891F92","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a93f13262bc300fba769190aafdb0940400641e6","datavalue":{"value":{"entity-type":"item","numeric-id":4888749,"id":"Q4888749"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1869745$5EEB1950-0FD9-47FD-8C49-0BC19A2806D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"854bf29386092635a477e0881f3f0c76f5ed2664","datavalue":{"value":{"entity-type":"item","numeric-id":5624995,"id":"Q5624995"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1869745$C68F3508-C9FF-47B6-90A6-17366B612FE2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"432f528cc4d5250dc24d614afd0d0830a051e95d","datavalue":{"value":{"entity-type":"item","numeric-id":2265602,"id":"Q2265602"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1869745$CE922422-1957-4477-BBD5-7046B9DD9C9B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6a8dc6fe306fb6128f6a04d961122f41facb7119","datavalue":{"value":{"entity-type":"item","numeric-id":4055156,"id":"Q4055156"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1869745$056B527A-E1AD-485A-8C3A-6E3D5D25CFB6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4534d792f5262a1f297a74f9b43efedcc5cd94ec","datavalue":{"value":{"entity-type":"item","numeric-id":4760022,"id":"Q4760022"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1869745$CA2C4B26-57FD-4050-B3E7-B3678C02F9E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e0abb6a683a9358701a72890e1300dfb39eb46ef","datavalue":{"value":{"entity-type":"item","numeric-id":1328753,"id":"Q1328753"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1869745$F14EAC9A-106A-4B5F-90E7-365F8E5E2125","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cb6ee5b448f0d24d59f4576742a6c8be5d2ca318","datavalue":{"value":{"entity-type":"item","numeric-id":4252321,"id":"Q4252321"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1869745$0406F915-2DCC-491C-A21D-6AFF79C84382","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"578954a8ceca39888f7914a7b02b99f9851e5da4","datavalue":{"value":{"entity-type":"item","numeric-id":4327634,"id":"Q4327634"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1869745$5AB18A26-4869-4E40-AD7A-A9B8FDA56612","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d05652188e444fc35e748b68b983451566933e27","datavalue":{"value":{"entity-type":"item","numeric-id":4856179,"id":"Q4856179"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1869745$0CCF4CA4-1D0B-4104-AFDB-8A4E150EBE82","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bae6bf27ae4115e161f6a12e1cf8eaedd382fe89","datavalue":{"value":{"entity-type":"item","numeric-id":4952638,"id":"Q4952638"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3d273994209725fea3d4b23cfde92c068c1e26d6","datavalue":{"value":{"amount":"+0.9940422773361206","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":"Q1869745$B2C2E608-B58E-4E66-AAD6-525CFBB30232","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cdc1462665046088928bcb7786e6b1120c3d249b","datavalue":{"value":{"entity-type":"item","numeric-id":4252321,"id":"Q4252321"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3d273994209725fea3d4b23cfde92c068c1e26d6","datavalue":{"value":{"amount":"+0.9940422773361206","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":"Q1869745$D51F9ADF-C5F6-4976-B043-EF1982550011","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bba87ec70996a00ee3ef1b4d5d79a8deaf51c652","datavalue":{"value":{"entity-type":"item","numeric-id":5946120,"id":"Q5946120"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6006e068fa7cee5d86eb676f662485270bbb0e11","datavalue":{"value":{"amount":"+0.8511825203895569","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":"Q1869745$75095C93-C72C-415F-9E95-8FC5DF4AAB05","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9eb1d6f6eee81399c9296aefd23b85811fdabc14","datavalue":{"value":{"entity-type":"item","numeric-id":5060129,"id":"Q5060129"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6006e068fa7cee5d86eb676f662485270bbb0e11","datavalue":{"value":{"amount":"+0.8511825203895569","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":"Q1869745$E0CC500E-EEA9-442A-906D-630F6180FA9B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e242520555bf383e1607ae2e9f03c76643ab0a5d","datavalue":{"value":{"entity-type":"item","numeric-id":1328753,"id":"Q1328753"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8fb3307b62e10638f6eaee092b6f5eab06ce8000","datavalue":{"value":{"amount":"+0.8485100865364075","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":"Q1869745$153541FC-7433-4C73-AE4B-FC74A202E058","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1869745","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1869745"}}}}}