{"entities":{"Q1198006":{"pageid":1208755,"ns":120,"title":"Item:Q1198006","lastrevid":66846849,"modified":"2026-04-12T13:15:19Z","type":"item","id":"Q1198006","labels":{"en":{"language":"en","value":"Approximate decision algorithms for approximate congruence"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 92079"}},"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":"Q1198006$AE104F75-4A0B-46FE-A4DC-6F16A1827294","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"dd1418b50ddbe99c3645a58fa8d4e929adb9b482","datavalue":{"value":{"text":"Approximate decision algorithms for approximate congruence","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1198006$5DB36972-18AE-4F72-BDC8-2C1551712EF2","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"d98c1fe2d56395cc4932f16e5db8eee206ccab70","datavalue":{"value":"0773.68073","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1198006$C8418CD2-1287-46F0-8F17-5F5DD6A18F70","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"ed74bc0d489d6087c42fdd3b765c9d9fb58efe81","datavalue":{"value":"10.1016/0020-0190(92)90025-Q","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1198006$1C2B618C-831A-445D-A112-C0B4067654DC","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"05eea7654cb0d0157b7f1411c545a76a3d53873a","datavalue":{"value":{"entity-type":"item","numeric-id":655161,"id":"Q655161"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198006$0E96DFBC-C6AB-4386-80C9-CADA21662003","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":"Q1198006$89AE1523-16F8-4CAE-9E26-879A17A3C009","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"be1a65edbb43ce1fc59464f99e70afbd93e8e2a0","datavalue":{"value":{"time":"+1993-01-16T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1198006$EB2C5B76-E058-4E73-80B3-B6CA8B59312A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"8867e016ab4114af947c5db607a62bf9a04eb62a","datavalue":{"value":"We derive a \\(({1\\over 2} \\varepsilon_{opt}(A,B), \\varepsilon_{opt}(A,B))\\)-approximate algorithm for approximate congruence by translations with running time \\(O(n^{2.5})\\) and a \\(({1\\over 2},\\varepsilon_{opt}(A,B) \\varepsilon_{opt}(A,B))\\)- approximate algorithm with running time \\(O(n^ 4)\\) for the general case.   An additional input parameter \\(\\gamma\\leq\\varepsilon\\) is used as tradeoff between running time and size of the indecision interval. We give a \\((\\gamma,\\gamma)\\)-approximate algorithm with running time \\(O((\\varepsilon/\\gamma)^ 2 n^ 4)\\) for the general case. The comparable (\\((0,0)\\)-approximate) algorithm of \\textit{H. Alt}, \\textit{K. Mehlhorn}, \\textit{H. Wagener} and \\textit{E. Welzl} [Congruence, similarity, and symmetries of geometric objects, Discrete Comput. Geom. 3, 237-256 (1988; Zbl 0679.68070)] has running time \\(O(n^ 8)\\). Furthermore we give a \\((\\gamma,\\gamma)\\)-approximate algorithm with running time \\(O((\\varepsilon/\\gamma)^ 2 n^{2.5})\\) for testing approximate congruence by translation. Here the comparable algorithm of H. Alt, K. Mehlhorn, H. Wagener and E. Welzl [loc. cit.] has running time \\(O(n^ 6)\\). Recently, \\textit{P. J. Heffernan} [The translation square map and approximate congruence, Inform. Process. Lett. 39, 153-159 (1991; Zbl 0735.68084)] has given a \\((\\gamma,\\gamma)\\)-approximate algorithm with running time \\(O((\\varepsilon/\\gamma)^ 6 n^ 3)\\) for approximate congruence by translations.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1198006$B37F1CD5-444F-4290-B3F5-34FF39C4989B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"159426a5937e62cfbbcc198dd4848ab52d6e715e","datavalue":{"value":"68U05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1198006$8A489147-96AF-4D83-B58A-A1AE5BDA9304","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"436b3ff85fb73aeacaf238296ef662d3527eb183","datavalue":{"value":"92079","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1198006$86458708-BA15-4840-B80F-F9E4522D540A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6cc5918892b50010a90ee07fa121a8c66268a4b7","datavalue":{"value":"computer vision","type":"string"},"datatype":"string"},"type":"statement","id":"Q1198006$F59BBB6C-6570-4488-A6CF-A35C7112A534","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d4b2794ddff7cfacb86e1dd5a96f98c64dcc39cd","datavalue":{"value":"point matching","type":"string"},"datatype":"string"},"type":"statement","id":"Q1198006$B38A367C-E545-43DA-AFD0-435591BDF228","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":"Q1198006$1A6B1910-156E-4BB8-964C-2357B3108A2F","rank":"normal"}],"P223":[{"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":"Q1198006$A52FF317-9B88-4D62-9F8C-7A737C397B98","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7121841971fb2fcfa42fe2054f14c0176f047adf","datavalue":{"value":{"entity-type":"item","numeric-id":3219798,"id":"Q3219798"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198006$091F2E42-3AEA-4DE9-AE55-69C21678B9CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6f51db3a5b60e65d71b6ce20daf130279be32405","datavalue":{"value":{"entity-type":"item","numeric-id":1182089,"id":"Q1182089"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198006$2D49AC58-61B3-4495-99E4-A25D04379578","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eea91ec7c3d1b7e77147b949d02ae1e71158d784","datavalue":{"value":{"entity-type":"item","numeric-id":3997848,"id":"Q3997848"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198006$BFD3F830-E72B-4B6C-AA24-A6D5434F5EA2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5d92b29d8bdfc4c5737905c6edddd77bef00045f","datavalue":{"value":{"entity-type":"item","numeric-id":3943552,"id":"Q3943552"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198006$8BE5C82B-A2E5-4E6C-85ED-AE72A666996B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"85b870ff096cd9b7374b71a9c8fe8f62feec4207","datavalue":{"value":{"entity-type":"item","numeric-id":3219752,"id":"Q3219752"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198006$9F1AE9D8-F4F6-49C1-B998-E1F202AB88A3","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"e9d5abe03719012c5595c62d55068c0d193a9623","datavalue":{"value":"https://doi.org/10.1016/0020-0190(92)90025-q","type":"string"},"datatype":"url"},"type":"statement","id":"Q1198006$94E0B086-A708-417A-935A-2A8D22E4508F","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"77fa5b884d693b511010d23a22219f1e4ec89237","datavalue":{"value":"W1980771011","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1198006$282A22AD-8A42-4D11-8AB2-975F07BFEC47","rank":"normal"}],"P1643":[{"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":"5d6ede2ddb49ed6094dfc516f7e21923b4839f6f","datavalue":{"value":{"amount":"+0.8356350660324097","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":"Q1198006$F7A03106-7583-4278-BB15-8FC5AD6051F6","rank":"normal"},{"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":"2953fd0e0fbc7c25f0d9f8c9f04b06ed9c648232","datavalue":{"value":{"amount":"+0.8325999975204468","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":"Q1198006$80AB1B0C-E070-4DF1-878D-74AB788195CA","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":"5af8db638e0f80b100423efde9ab2089534ef722","datavalue":{"value":{"amount":"+0.815617561340332","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":"Q1198006$C586F346-268E-4CFE-A32C-F3C62F02DE4D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"de663b5c9f17a6e8f957eec87e20b5023612ca42","datavalue":{"value":{"entity-type":"item","numeric-id":1182089,"id":"Q1182089"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0b33407166303c6587dd7bbdbd1d424b0fa69a9b","datavalue":{"value":{"amount":"+0.7915191054344177","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":"Q1198006$5974BCE4-28A5-4B75-A9C7-F2F49141E117","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e4649ac776e39695c281f3d88967f7ffc2bab54a","datavalue":{"value":{"entity-type":"item","numeric-id":4728246,"id":"Q4728246"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2436cbf03331d3c34dea443f3c57b1deef94fbf9","datavalue":{"value":{"amount":"+0.7905820608139038","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":"Q1198006$0DCC0D74-5668-445C-946F-1C8EA6FC8FE9","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Approximate decision algorithms for approximate congruence","badges":[]}}}}}