{"entities":{"Q654290":{"pageid":656139,"ns":120,"title":"Item:Q654290","lastrevid":51392444,"modified":"2026-01-18T01:35:46Z","type":"item","id":"Q654290","labels":{"en":{"language":"en","value":"A general approach to the analysis of controlled perturbation algorithms"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5992345"}},"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":"Q654290$D21A8EAD-22F5-4A74-91A5-3A741F2A68E1","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"30e2b64bb7ae410e8cbda98bc37266ab3264cb62","datavalue":{"value":{"text":"A general approach to the analysis of controlled perturbation algorithms","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q654290$9698DB9B-7C73-46DC-BA1B-B74C41B6B7BA","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"85129b08c8dcb16dfee2bf6ec5a5f4817144d8b9","datavalue":{"value":"1247.65024","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q654290$F6C7D411-F58E-43ED-B86F-E66D047951D7","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"93f2bc7106f436b3e95136cb7027e49039db559e","datavalue":{"value":{"entity-type":"item","numeric-id":270030,"id":"Q270030"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q654290$745D6556-3932-4889-9FCC-D631E1A833F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"805c1ab5f45638df1a9f7bfcc1e0d6168782f7f2","datavalue":{"value":{"entity-type":"item","numeric-id":654289,"id":"Q654289"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q654290$2EE38821-8360-4E1E-948F-AF6BB12CC91E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"2af1a2a8fdd599806ebb57198f11dea8f8491046","datavalue":{"value":{"entity-type":"item","numeric-id":325153,"id":"Q325153"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q654290$6D6B2B00-7693-4D88-A2C6-4C0EB262135E","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":"Q654290$5348F97E-9F85-4DEB-A032-1A606E7F6F21","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"b21ce3e91b828a476728b1fb914374690f57463f","datavalue":{"value":{"time":"+2011-12-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":"Q654290$36E4B59E-2D68-4394-AFFE-7E9981607F2E","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"9d2102663fb8a968b63f6cc1abcdf1353344df7f","datavalue":{"value":"The implementation of a clear geometric algorithm always has to solve the following problem: On the one hand, computing with rounded arithmetic may question the reliability of programs while, on the other hand, computing with exact arithmetic may be too expensive and hence inefficient. One possible solution has been proposed in the recent past years: the implementation of controlled perturbation algorithms which combine the speed of floating-point arithmetic with a protection mechanism that guarantees reliability, nonetheless.  In the paper under review the authors present a general methodology for analyzing controlled perturbation algorithms considering the perturbation amount, the arithmetic precision, the range of input values, and the number of input objects. Some examples are studied in detail: the distinctness of points, the 2D-orientation predicate, the orientation test in D-space and the common intersection point of three circles in the plane. The methodology is powerful enough to analyze all geometric predicates that are formulated as signs of polynomials. Nevertheless, in a future work the authors want to extend the analysis from polynomials to rational functions or expressions involving square roots, or to make controlled perturbation applicable not just to sets of points, but to problems whose input has a combinatorial structure.","type":"string"},"datatype":"string"},"type":"statement","id":"Q654290$19920C61-58AA-47CA-A8A3-201E088465A2","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"2ce72165d993b0b8ed97728d731d2db2473b9554","datavalue":{"value":"65D18","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q654290$FF8E754F-70FF-42A5-8B85-AD09B17AC385","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"e5df2ccbb285b9cc5a9961422b3dd9b5d5c268ff","datavalue":{"value":"5992345","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q654290$47687C61-BC8D-4F4B-A6C9-5293EB960664","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1dc8584f0b1a0a048ecf0edd2b7b0b560816ad7c","datavalue":{"value":"reliable geometric computing","type":"string"},"datatype":"string"},"type":"statement","id":"Q654290$52799FA2-C4B4-477E-B5D7-92EE751598EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a16f45c1fb4f8912d910c07b9c56c75975577e6d","datavalue":{"value":"controlled perturbation","type":"string"},"datatype":"string"},"type":"statement","id":"Q654290$46244986-C134-4FAE-B7C2-57B70EDAFB0C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"db0d1371366f9f64f22346801a97b77bd5cd943a","datavalue":{"value":"floating-point computation","type":"string"},"datatype":"string"},"type":"statement","id":"Q654290$59A752C6-ECF0-4A45-8A64-54251689973B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2e00677f8be0088974fc995adee74d58f924c005","datavalue":{"value":"numerical robustness problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q654290$87408464-476E-4ABB-BA67-2A65059E0844","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"48ddf43eca498c7e7087cd696beb82ea63925320","datavalue":{"value":"algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q654290$4038CAC8-9BAC-459A-97AD-F37998FF1E3F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"458f12def83c1367a32fd7e7e1dd4b0d57985296","datavalue":{"value":"orientation","type":"string"},"datatype":"string"},"type":"statement","id":"Q654290$EB2EF6FC-BAF2-438A-AB25-55F33738B1BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6e12b32b698874a31f3d4380014dab79b44e8c67","datavalue":{"value":"intersection point of three circles","type":"string"},"datatype":"string"},"type":"statement","id":"Q654290$097DDB0E-368E-493D-B560-C7F1A0E61930","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7772b2099bc6d26f76826dbfb2c6395643448009","datavalue":{"value":"geometric predicates","type":"string"},"datatype":"string"},"type":"statement","id":"Q654290$09AF0E9D-25AD-4A60-824F-42E4C56F79F7","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"cddb9b56278140b4e4b3e2560891aea6b6cd8a4b","datavalue":{"value":{"entity-type":"item","numeric-id":478831,"id":"Q478831"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q654290$EC870BC6-774C-4875-B42E-3075796180D7","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"be8017d9dbdcd2a09b059a0646cab651cb922afd","datavalue":{"value":{"entity-type":"item","numeric-id":12888,"id":"Q12888"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q654290$3661CA1D-5E77-4FF4-93FC-4B5DF80EC3C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1463","hash":"8970d53f5fc5de8a7599b5d4b50f76cbd183814b","datavalue":{"value":{"entity-type":"item","numeric-id":13265,"id":"Q13265"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q654290$259B642F-C1F7-4A93-8477-9F9F00879AC4","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":"Q654290$9BFE1F45-9CF9-4378-A2DB-34921334CB1B","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"8172fbbedc1b0102b01c88891fc276bab2688710","datavalue":{"value":"https://doi.org/10.1016/j.comgeo.2011.06.001","type":"string"},"datatype":"url"},"type":"statement","id":"Q654290$B264EFE1-46C0-4BE5-B752-AC05C4DE1F8B","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"9187a255373912d5839f0bc02248ec70e3d9ff8a","datavalue":{"value":"W2004412712","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q654290$158FA7D4-07BB-4B26-AC20-E831CACB074D","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"e07bd7c123f3cd6cc472e934ba6b9435a41ef7d2","datavalue":{"value":{"entity-type":"item","numeric-id":4682167,"id":"Q4682167"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q654290$C66D9B2C-BF8C-4B1A-9683-2B1F03F70867","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f215e26473d7ee7302acfe5b220f36e8fab580a4","datavalue":{"value":{"entity-type":"item","numeric-id":1364354,"id":"Q1364354"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q654290$F1FE9F2F-D604-4BEA-B9C5-D9BF61970281","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"83eade82042e507248d4b50c48d61d395faceaeb","datavalue":{"value":{"entity-type":"item","numeric-id":3358264,"id":"Q3358264"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q654290$CD4707AD-DBD9-4443-AD7D-6D11BEF31604","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eeb1cfc40dfd182f66e3a0f632818e8586ae9dbd","datavalue":{"value":{"entity-type":"item","numeric-id":2921776,"id":"Q2921776"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q654290$E89B8025-BA03-45C7-BFC4-A71CDEF6EE54","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"de278d257ea858d2135195c0787ac42e8d8a985a","datavalue":{"value":{"entity-type":"item","numeric-id":4824660,"id":"Q4824660"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q654290$D570B000-DA0F-4230-A1F2-DED08672D86E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1f8eee8ffd50970129f1481e0b39c50c56694191","datavalue":{"value":{"entity-type":"item","numeric-id":1265287,"id":"Q1265287"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q654290$5E7BDF5C-917E-4BD7-93A1-0755CBD325CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b813ac28bac9e26360ed3bd466acc1fde8fb07d3","datavalue":{"value":{"entity-type":"item","numeric-id":1179540,"id":"Q1179540"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q654290$0722FC92-545C-47BA-9709-BC0349E0B903","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"08134b8e62091d5e80f4a82e048d0a86cff8d297","datavalue":{"value":{"entity-type":"item","numeric-id":5464628,"id":"Q5464628"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q654290$C1FE3B66-93F5-4DD2-AF27-6B50439FD8E9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dc6482fda869c7df0ed32fd6ade8f790a1ff04cc","datavalue":{"value":{"entity-type":"item","numeric-id":5585020,"id":"Q5585020"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q654290$941D7852-B64D-4C3B-ABEE-6D824891EBDF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"de431ae5e1e6d0bce50265c8838d96541539c883","datavalue":{"value":{"entity-type":"item","numeric-id":4702188,"id":"Q4702188"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q654290$699F9FE6-87A5-4C77-A85F-B791741F6B5B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c1aacbce8e8db65b7623db0eae2c85f1a4906b1f","datavalue":{"value":{"entity-type":"item","numeric-id":3613768,"id":"Q3613768"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q654290$6A963CA6-F580-4A81-ADD4-4BC1018B102A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d324397944ab5b3b55df242afc54ca11e2805183","datavalue":{"value":{"entity-type":"item","numeric-id":1380782,"id":"Q1380782"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q654290$DC725D14-C17D-485E-9B2C-E0068D0CBB66","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e951111940a87d282789c7f78b06d3202b911828","datavalue":{"value":{"entity-type":"item","numeric-id":5254193,"id":"Q5254193"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q654290$EA2FEE2B-D9CF-4816-B547-88F2183FAEB2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5fec62e1b4f8979cbacbdfbba04f8919689605ab","datavalue":{"value":{"entity-type":"item","numeric-id":918201,"id":"Q918201"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q654290$AA4E1AEC-7935-4E83-A971-38B32BD8104D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"be448ead31ba76a82a0ee46466ebc36ef990d168","datavalue":{"value":{"entity-type":"item","numeric-id":676577,"id":"Q676577"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q654290$8A43456B-DBA2-45C6-A180-595A562DAB9D","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"58b467df85b94394b394d916b815f987788eac6b","datavalue":{"value":"10.1016/J.COMGEO.2011.06.001","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q654290$ADB8E7F4-8600-4EB5-9DD2-1938F99199DF","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2480615af809d8014bfa2de66757e7df081fb0f2","datavalue":{"value":{"entity-type":"item","numeric-id":3613768,"id":"Q3613768"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"21d4e9d3d1520439857403b0463b6f726e850d15","datavalue":{"value":{"amount":"+0.8788121342658997","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":"Q654290$F87AB612-3557-419B-ADA3-6B4D4F811727","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c609ddc87e276f431a8615267f03c84a634cd5f8","datavalue":{"value":{"entity-type":"item","numeric-id":5747867,"id":"Q5747867"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b6debf7c920853c459e79e273cef74340ce46038","datavalue":{"value":{"amount":"+0.8722010850906372","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":"Q654290$9DB1213D-C7D0-411E-9D72-0CDF762FDE9D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f13ea73ed50d4f721920343bb438c99b9cc905ba","datavalue":{"value":{"entity-type":"item","numeric-id":2921776,"id":"Q2921776"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"da3fbe39bb42d29fb8bd0b5f316418aec0a58b58","datavalue":{"value":{"amount":"+0.861968994140625","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":"Q654290$F70E73A5-66AD-4B81-A96C-0A926E1E0ED7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f78b76a8a785019fb1bc68fff3031fc2d35f80a7","datavalue":{"value":{"entity-type":"item","numeric-id":3434535,"id":"Q3434535"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8eec838df958a8a9a019321897d7c09cd54c6139","datavalue":{"value":{"amount":"+0.8558101058006287","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":"Q654290$6D8659E0-F06D-4203-B3D5-1F947BFE0AAE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"88196502e87c5f2dfc36058c5674176056a192a2","datavalue":{"value":{"entity-type":"item","numeric-id":543787,"id":"Q543787"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"33a2020c63159ea6fe32bf8936c517c61182e18c","datavalue":{"value":{"amount":"+0.8061951994895935","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":"Q654290$AB78DC29-8557-455B-9DCF-3F643F3C0AAB","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:654290","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:654290"}}}}}