{"entities":{"Q972846":{"pageid":974694,"ns":120,"title":"Item:Q972846","lastrevid":42794400,"modified":"2025-07-11T13:33:30Z","type":"item","id":"Q972846","labels":{"en":{"language":"en","value":"Faster algorithms for computing Hong's bound on absolute positiveness"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5710827"}},"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":"Q972846$D96F7FE3-6EAF-4ED9-8447-113E8B8B3513","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ee4907344485eff0bac068c4cab8b669d9b6a6a9","datavalue":{"value":{"text":"Faster algorithms for computing Hong's bound on absolute positiveness","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q972846$F22DC4E2-B1E3-44DE-AA94-D202CFC3B7E4","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"02521a8fc7447167e96d76998d06a90d483bf62f","datavalue":{"value":"1206.11151","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q972846$D174401F-7B00-4D05-B222-D507A3F5B974","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":"Q972846$4FD0C932-AF0D-4BE1-B827-BD2DC458B783","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"8353e036d7c7c3a124e51c0b0df2d09f1d943a23","datavalue":{"value":{"entity-type":"item","numeric-id":265722,"id":"Q265722"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q972846$3CA5F4EB-3941-4FAA-B62D-5F72EF4F66FF","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ea72303f92787da89554ee5fa15621068821a762","datavalue":{"value":{"entity-type":"item","numeric-id":99061,"id":"Q99061"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q972846$3016635D-8210-44F8-A6C6-E688CF3894DA","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"55bff1cde4af9ec013d98855f36c47ee535bd8b2","datavalue":{"value":{"time":"+2010-05-21T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q972846$41EEDAB2-8C6B-411F-B94B-C52F8392FCBD","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"0c2b2293068e481d126e4ed50f19e86fda388a3f","datavalue":{"value":"Hong's bound is a bound on the absolute definitiveness of a real polynomial \\(f\\) in \\(d\\) variables. It gives a bound on the region where \\(f\\) and all its derivatives are positive. Let \\(n\\) be the number of monomials of \\(f\\). The obvious way of computing Hong's bound has time complexity \\(O(dn^2)\\); in this paper the authors improve this to \\(O(n\\log^d n)\\). This result is achieved by representing the computation as the determination of the \\textit{lower hull} of a set of points: the lower part of the convex hull. In the univariate case, \\(d=1\\), they even achieve an optimal result, time \\(O(n)\\), by mixing the computation of lower hulls with Hong's formula. As application an improvement in the continued fraction method of root isolation is mentioned.  Correction text: We show that a linear-time algorithm for computing Hong's bound for positive roots of a univariate polynomial, described by the second and the third author in an article [ibid. 45, No. 6, 677-683 (2010; Zbl 1206.11151)], is incorrect. We present a corrected version.","type":"string"},"datatype":"string"},"type":"statement","id":"Q972846$AE9D082A-87EA-46AE-9889-34BD39DFEA8A","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"1ed379caba5272270a891362ebcbe3310f9391b8","datavalue":{"value":{"entity-type":"item","numeric-id":841238,"id":"Q841238"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q972846$10243448-A6C6-4092-8F4D-E690063F5B36","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fd716104cf156585f3bce22202c836b7465d3133","datavalue":{"value":"11Y16","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q972846$292FA1AF-7FFC-414B-96E8-7AE6FF75DAEC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a1448dc8abee9c87d433fb284555380dc61ce707","datavalue":{"value":"12D99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q972846$FCAD4081-A105-4704-9444-C606D94A8D05","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"56c7f76923b29a06e5df502ec9e72c901e9849fe","datavalue":{"value":"12E05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q972846$2FCFFDFC-C589-443C-ABCE-03C9FA314214","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"661c831991cdebd51f9465b74d929024bd00f373","datavalue":{"value":"12Y05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q972846$4C9FF3B7-7E21-4A22-8BB3-2D7B609672C2","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"705423913056418b889b9dbf48a297bd97763728","datavalue":{"value":"5710827","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q972846$5502D46F-85A5-4E03-A92F-CFA54F1A6CC3","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4875849e7410ac4ff593a4642711c87df21a8c87","datavalue":{"value":"Hong's bound","type":"string"},"datatype":"string"},"type":"statement","id":"Q972846$E1348C57-2E47-4A3A-8B8E-B9ED06DCA9C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2ffc6eceb71984badccb37483fa4cdeee1cd5be2","datavalue":{"value":"absolute positiveness","type":"string"},"datatype":"string"},"type":"statement","id":"Q972846$20BC2A8F-73D1-405D-86C6-67F3C431FAF7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8034350ab85a2be2001a0e942542d457fe0032a4","datavalue":{"value":"geometric computing","type":"string"},"datatype":"string"},"type":"statement","id":"Q972846$0CF412E9-6C62-452D-9E2C-03E8279AAD9C","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":"Q972846$CAC73AF3-A664-40D2-9A89-BFB05A574BDF","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"6d9c507b884af9f35de3bb9f2b68aeb0e4fdc25b","datavalue":{"value":"https://doi.org/10.1016/j.jsc.2010.02.002","type":"string"},"datatype":"url"},"type":"statement","id":"Q972846$E029B1E4-9FD0-412C-A34E-9B286E745324","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"ce7674d38f0b7059bccaaeeb456e94480da66473","datavalue":{"value":"W1968804058","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q972846$42B80358-3715-491C-BD47-2AFFC0DAEBDC","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"2ae4767e0ce001e13ea4d79e31760f7397cbb2d7","datavalue":{"value":{"entity-type":"item","numeric-id":3535915,"id":"Q3535915"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q972846$DAD9958E-C82F-4092-B00B-6D4266E9E417","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d0d029af071a8946ee1662887e0e0b0ab0a7ae3b","datavalue":{"value":{"entity-type":"item","numeric-id":4344150,"id":"Q4344150"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q972846$4E04927E-B40B-4684-AAB3-FF33812497F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"360ea86db54a240882fd7852c5d4539a6820482e","datavalue":{"value":{"entity-type":"item","numeric-id":1264464,"id":"Q1264464"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q972846$FD53D49F-0916-4885-B436-3AB7508E4F30","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dc4e4810c58cad42b4089504215405436e399a63","datavalue":{"value":{"entity-type":"item","numeric-id":2378508,"id":"Q2378508"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q972846$47DE37A4-1CEF-40FA-98A0-089FDA48AAA5","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c17cb403cf21dc019d4bf94f3f5f794b23189ebe","datavalue":{"value":"10.1016/J.JSC.2010.02.002","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q972846$C5A24F9E-6DA4-4F2B-91A5-009F8DCA003A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P27","hash":"6323b55ccf70737062cbdc0f599aeb8ff7356385","datavalue":{"value":"10.1016/J.JSC.2017.05.008","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q972846$8AE606B3-80C2-4928-9CE1-9DA17CC7D56A","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f0523f4fbdcf39bf987803ad93448c40aeb33cde","datavalue":{"value":{"entity-type":"item","numeric-id":1690791,"id":"Q1690791"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cd45ee4be6be0f6b0aaa8efbf7a92001f18bc46c","datavalue":{"value":{"amount":"+0.9281471","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":"Q972846$0B41AACB-6B66-4B00-B245-50C247C26593","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bf88a61a004044c1a8591b028c52949f7c9a8a90","datavalue":{"value":{"entity-type":"item","numeric-id":5167553,"id":"Q5167553"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e9f52cd0966b8fc9620217a3ac50a520967bc3b7","datavalue":{"value":{"amount":"+0.8408127","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":"Q972846$BD914A42-6AE1-4D90-A444-49BCD1277414","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2eb4a8cf8f5bb4cfdfd3a3970bec9ae668561286","datavalue":{"value":{"entity-type":"item","numeric-id":2427477,"id":"Q2427477"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d1f59ac0c6cc9485dfdeae9eb9355677f5555dcf","datavalue":{"value":{"amount":"+0.8397423","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":"Q972846$F77BD1C4-5806-4D0D-A185-25D0EBB2B625","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3ef540e9393cbde1ad989d2e38a0d27252c54f53","datavalue":{"value":{"entity-type":"item","numeric-id":3052836,"id":"Q3052836"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"de417ccf12e7d6dafbd58708a6edc7a158f8abde","datavalue":{"value":{"amount":"+0.83772135","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":"Q972846$26299465-E0FC-4A3F-B213-80ED826C58E7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"34b8a7516435aae761d5450e8c8472fdfe0f759f","datavalue":{"value":{"entity-type":"item","numeric-id":5712453,"id":"Q5712453"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6005b08e4a09d37a3fb22bc374bf5aacce202d37","datavalue":{"value":{"amount":"+0.83728707","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":"Q972846$B24E0C69-410F-4A4A-A341-E06E991CF077","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6bb3773ea92a6164d749b8d5ac02379678596bf2","datavalue":{"value":{"entity-type":"item","numeric-id":1281503,"id":"Q1281503"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7aeb5f3697878c4ec16a598ad8578f879e652371","datavalue":{"value":{"amount":"+0.8370584","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":"Q972846$249F88AB-EF07-45A7-9DC9-D8CB78818E7D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"67c1814ac90571de5dee4adcc9781d815c8279d8","datavalue":{"value":{"entity-type":"item","numeric-id":4620318,"id":"Q4620318"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d967e5647d1a07c4d23c493364bb6e072c0bbfa1","datavalue":{"value":{"amount":"+0.83184254","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":"Q972846$FC6A19E7-8730-4252-953C-5CFD8A32B37A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2025b1d547da36739b8cc477d6dba51c6727995c","datavalue":{"value":{"entity-type":"item","numeric-id":1334675,"id":"Q1334675"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1bd1a864d54fe2b672265d95ed15ba6c61e74b52","datavalue":{"value":{"amount":"+0.82985353","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":"Q972846$19E0F2D3-09E3-436F-B87C-53C641DFE93A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dea3fe7108003828dfe2a80f802eb2fa4cd5970d","datavalue":{"value":{"entity-type":"item","numeric-id":401316,"id":"Q401316"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"62be4180da45ca5fa86f7cb7129727017f341f93","datavalue":{"value":{"amount":"+0.8288467","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":"Q972846$F66C05CB-761D-47FE-B0BD-2FEC0451AA36","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"333dde3efd46ca42afaa71695d728914d223bf84","datavalue":{"value":{"entity-type":"item","numeric-id":5957271,"id":"Q5957271"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f0352bd96d6ff25e9d5a67d2eb60e61a22cb96c8","datavalue":{"value":{"amount":"+0.8288288","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":"Q972846$1E6DF879-BDF7-457A-B6B6-0619B3829E3A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:972846","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:972846"}}}}}