{"entities":{"Q722361":{"pageid":724210,"ns":120,"title":"Item:Q722361","lastrevid":63876480,"modified":"2026-04-11T16:08:40Z","type":"item","id":"Q722361","labels":{"en":{"language":"en","value":"Covering compact metric spaces greedily"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6909530"}},"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":"Q722361$5CC5CD57-AA66-4DF8-B95B-5F0199611029","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"dbf271aa50fa5c32eb89f111eb670e0e73c77b74","datavalue":{"value":{"text":"Covering compact metric spaces greedily","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q722361$DDD7CE62-E92C-494F-A48C-42F8391B934A","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"723f1c784ffca5fe2b9498118823173da12f3bee","datavalue":{"value":"1459.52015","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q722361$E89BEC5B-CB64-45D1-9495-640B44485BD9","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"2383d2451ec69d5866e50c1bef4ccb455c8617f9","datavalue":{"value":{"entity-type":"item","numeric-id":722359,"id":"Q722359"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q722361$BBD2206D-BBB4-4C84-9D33-12E727157C6E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"301675512b8ea2138691ab4ee978fd6274a8d631","datavalue":{"value":{"entity-type":"item","numeric-id":344927,"id":"Q344927"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q722361$281A72FC-8B97-48D4-92A0-E74524223EDE","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"4b942190e17083b575cb45317653fe779fdb5a77","datavalue":{"value":{"entity-type":"item","numeric-id":168571,"id":"Q168571"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q722361$CE946222-FB55-441C-9590-40A383559D64","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"fc8ead1e0a28b70e88525b0ff5541d1c12dd7ebc","datavalue":{"value":{"time":"+2018-07-23T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q722361$9BCD3BF5-74B1-40C7-8D36-00AD7F5DBF3B","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"92af85d863505fc009df25ab003f1f0d6e48add6","datavalue":{"value":"https://arxiv.org/abs/1710.06002","type":"string"},"datatype":"url"},"type":"statement","id":"Q722361$3A455B32-DE38-4581-9DB1-5E3C4AC78E88","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"f3705afaff7709eedd7ff5a26365a829872585d0","datavalue":{"value":"Let \\(X\\) be a compact metric space with metric \\(d\\) defined on it, and write \\(B(x,r)\\) for the closed ball of radius \\(r\\) with respect to this metric centered at \\(x\\) in \\(X\\). The covering number \\(\\mathbb N(X,r)\\) of \\(X\\) is defined to be the smallest number of balls of radius \\(r\\) needed to cover \\(X\\). The paper under review is concerned with obtaining bounds on \\(\\mathbb N(X,r)\\) for a compact metric space \\(X\\) carrying a probability measure \\(\\omega\\) on it, i.e., a Borel measure normalized so that \\(\\omega(X) = 1\\). This measure is assumed to be non-degenerate and homogeneous on balls throughout \\(X\\), hence write \\(\\omega_r\\) for the measure of a ball of radius \\(r\\). With this setup in mind, the authors prove that \\[\\frac{1}{\\omega_r} \\leq \\mathbb N(X,r) \\leq \\frac{1}{\\omega_{r-\\varepsilon}} \\left( \\ln \\left( \\frac{\\omega_{r-\\varepsilon}}{\\omega_{\\varepsilon}} + 1 \\right) \\right).\\] The proof of this result is based on a greedy algorithm, iteratively choosing balls to cover the maximal measure of the space yet uncovered. This greedy algorithm has previously been analyzed in the finite setting of the set cover combinatorial optimization problem, in particular by \\textit{V. Chvatal} [Math. Oper. Res. 4, 233--235 (1979; Zbl 0443.90066)]. The authors transfer Chvatal's argument to the setting of compact metric spaces to prove their theorem. Then they apply this theorem to three concrete geometric settings, retrieving some of the best known asymptotic results and unifying many results on sphere coverings.","type":"string"},"datatype":"string"},"type":"statement","id":"Q722361$117B9C7E-4965-4D24-B399-685117DD70BF","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"56e07a742632833799a0ee2e9f4be6eb5e8a1a34","datavalue":{"value":{"entity-type":"item","numeric-id":274715,"id":"Q274715"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q722361$F952E30D-DC61-41D3-9D59-411CC8F8D616","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4e1df7ba929664ba7b91d5a816f05411516abc3","datavalue":{"value":"52C17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q722361$83CE0628-CC35-4B88-BD6B-4AC42A4A9252","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"35cb8465ca85ba26995d54be2905dc35556d665c","datavalue":{"value":"90C27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q722361$7ADC8903-44A5-4B82-9EC2-5F24A2DB039F","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"26f86e03c1a06553df7a63e8e27c9a0e76077b43","datavalue":{"value":"6909530","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q722361$D3131FCE-33A9-4C70-B8C8-C16BCBE65E08","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ffab7a5d5afcf9b5a49e32a959b6cf584c6408a4","datavalue":{"value":"geometric covering problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q722361$2217F9B1-685D-4D0A-930A-8B627D45B813","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"985d6383219d2a224506d6f09330b5560ef81c74","datavalue":{"value":"set cover","type":"string"},"datatype":"string"},"type":"statement","id":"Q722361$A4C60C78-1B5F-4566-A2F2-1611CF14DE3E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3e1e7eb452ae4c92c43fa47bb0afb8177365a429","datavalue":{"value":"greedy algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q722361$C14C4E31-E844-46C2-8FC5-AD9904731555","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":"Q722361$6138B478-00CB-41AB-8706-03B0C1ED3C0A","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"92b337c3f5528b8d49f4129684689d3350a9aa26","datavalue":{"value":"W3100454277","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q722361$FD60B7D1-78BF-4A3C-8E5A-3C0FAC69F4F7","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"ee66f4fa21e8deb300c45482fe504c69d8fe9dc6","datavalue":{"value":{"entity-type":"item","numeric-id":531815,"id":"Q531815"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q722361$346A4719-9909-4A68-ABCA-B63A52D717CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1134e6196adc0354cf6a80289f0d9eef4966d4ff","datavalue":{"value":{"entity-type":"item","numeric-id":891149,"id":"Q891149"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q722361$F8DDD0BC-6D30-4838-9E26-A36AC2C2F033","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9920697b2550f7d3da4d17798f4a36adc95e4d70","datavalue":{"value":{"entity-type":"item","numeric-id":5692699,"id":"Q5692699"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q722361$597F9CCA-A802-41A6-BE77-4988135879E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5a80eed9f379f185c9ca92aab1fa2ad3cc4463c9","datavalue":{"value":{"entity-type":"item","numeric-id":3887227,"id":"Q3887227"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q722361$21BC3E7E-BFB4-4146-8255-729129032173","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5d2b873cef8d689666ce074150d519b9e742b37f","datavalue":{"value":{"entity-type":"item","numeric-id":2761194,"id":"Q2761194"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q722361$6BF4646A-18C4-44DF-90FC-571EB926C4A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d00a694d0f3c2004e75a830c958cf154ee868c4d","datavalue":{"value":{"entity-type":"item","numeric-id":5259598,"id":"Q5259598"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q722361$396146D4-827D-4AB7-A1C8-E1AD92B909C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e0f5268b311d5f40824a5975d079ec8f5c6c52e1","datavalue":{"value":{"entity-type":"item","numeric-id":2471717,"id":"Q2471717"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q722361$49024715-CDBA-4792-93E5-FB381AA77A7A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4f9972798b2a7bc9996adbe7182cc9d6bda821a3","datavalue":{"value":{"entity-type":"item","numeric-id":3182686,"id":"Q3182686"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q722361$41C7C8BB-6645-46A4-8B6E-0EFC37BD9FE3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d64807a789590f09c488efd989b4666bcb65ce98","datavalue":{"value":{"entity-type":"item","numeric-id":4255465,"id":"Q4255465"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q722361$387D1656-89E0-45C6-9D4F-2FF4EA3B3583","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"463c0a1f953688accd88945a3ff0ba7c453a3493","datavalue":{"value":{"entity-type":"item","numeric-id":351503,"id":"Q351503"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q722361$561BD02A-E35D-42EE-812A-DEC404CEC30B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4a567a0bd5149009c58baa277d371437f0fed769","datavalue":{"value":{"entity-type":"item","numeric-id":1213733,"id":"Q1213733"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q722361$4ECA9E62-80B6-4277-9662-05C8BC6C080D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7db3468346fcce29d2fe703e3816d1c0ffadbf3a","datavalue":{"value":{"entity-type":"item","numeric-id":1224109,"id":"Q1224109"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q722361$2ABF6A38-89E6-4637-8A2D-CB3F6C11D873","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4e4bdb026a65ab9d3f83ed603c3bf58ca28e8d61","datavalue":{"value":{"entity-type":"item","numeric-id":2809209,"id":"Q2809209"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q722361$E1AD4BFE-01F8-4FA3-8BDB-F62252988871","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c399bf3e76ad9530cfebab4679760a76f1ee16f9","datavalue":{"value":{"entity-type":"item","numeric-id":2408974,"id":"Q2408974"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q722361$37D8F0BA-7261-478A-A624-0E8CA8D4EE62","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4dd6e312ec79bbf754b72fb4d772a9cc06b8517c","datavalue":{"value":{"entity-type":"item","numeric-id":1783626,"id":"Q1783626"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q722361$16133196-C706-4C4C-A693-A855C5296D41","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e391041a85d1e9612197d6b6c0b07d23ac311188","datavalue":{"value":{"entity-type":"item","numeric-id":5568974,"id":"Q5568974"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q722361$B4749244-72CA-4166-B32E-1737F3E20371","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"37569370988d83c6e25e2408701daace1e7830a6","datavalue":{"value":{"entity-type":"item","numeric-id":1845725,"id":"Q1845725"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q722361$F383CD8D-F358-4D59-A6C3-1E1D65D8A900","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"d40702f8323c157793cf62a1c0d1123344b1a62d","datavalue":{"value":"Q129869620","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q722361$D3C35E79-BEEA-4DBE-9C1A-7ABA27E9B03B","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"0b588b78f812759b68a4214ed9bf8902fa22c061","datavalue":{"value":"10.1007/S10474-018-0829-4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q722361$A66C7D74-EB0A-40EF-9EB1-DCDED9D7AE98","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ccb5e293f4216ad72ed0891b7fa712b390416b3c","datavalue":{"value":{"entity-type":"item","numeric-id":5093989,"id":"Q5093989"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"eb32dee5c589d8e76687f7541f6d3fba8bf0e90b","datavalue":{"value":{"amount":"+0.7597725987434387","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":"Q722361$5A4A569E-E31C-4FE0-A914-2A863F8985B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c0a86bc5c72947220f5281f86f987dd1702a625d","datavalue":{"value":{"entity-type":"item","numeric-id":4249099,"id":"Q4249099"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5627db0e21a2f803a62d31b3ccad965403c18f1a","datavalue":{"value":{"amount":"+0.728628933429718","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":"Q722361$A1F465FB-2668-42AD-992A-8EE827FC98DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"10290975cd278ffd779b94d964edde9a5f31b0f8","datavalue":{"value":{"entity-type":"item","numeric-id":2809209,"id":"Q2809209"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"eb49f02ac5250835ca325d744d23f89330ab7e24","datavalue":{"value":{"amount":"+0.7281349301338196","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":"Q722361$8F424015-4A52-460A-BFA0-A5A7A8DEF044","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f00b030c93f6b3ac615fce002aa0a947c0837e84","datavalue":{"value":{"entity-type":"item","numeric-id":2471717,"id":"Q2471717"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1523bbb59bf4aa064ce0806102faf3f7737a491e","datavalue":{"value":{"amount":"+0.713531494140625","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":"Q722361$24B844E7-56E8-47FD-AEC2-824114107015","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"38eddbd5142657ee46b50cf1197b27243877ee68","datavalue":{"value":{"entity-type":"item","numeric-id":5752780,"id":"Q5752780"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a9e4d5b05351cfb11268d4149142e81f927d8fb5","datavalue":{"value":{"amount":"+0.7125837206840515","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":"Q722361$3DA51E93-6422-4CA3-A36B-C3E4A84B5F4D","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Covering compact metric spaces greedily","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Covering_compact_metric_spaces_greedily"}}}}}