{"entities":{"Q680146":{"pageid":681995,"ns":120,"title":"Item:Q680146","lastrevid":63539979,"modified":"2026-04-11T13:51:12Z","type":"item","id":"Q680146","labels":{"en":{"language":"en","value":"Approximation algorithms for the unit disk cover problem in 2D and 3D"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6828435"}},"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":"Q680146$E1AC756F-0E36-4ED7-A7D5-C36913D9CD6D","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b7b8db3f52ff23b18e94df867f80d2ff4f206725","datavalue":{"value":{"text":"Approximation algorithms for the unit disk cover problem in 2D and 3D","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q680146$68CCC048-66D5-4278-AE24-CC273981D78D","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"afa2e1eafae63f0bb5aaada4245f789d427f38bc","datavalue":{"value":"1385.65022","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q680146$E0961230-78D9-4CAF-A731-AC5868D5932C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"03146bb8e17b3d6cc14817a371f8c48ba30cf452","datavalue":{"value":{"entity-type":"item","numeric-id":624377,"id":"Q624377"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q680146$55107645-0EC5-458D-8F4B-3DA96824FAB7","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":"Q680146$49B32CC6-0E06-48DE-A950-055BEE8D152C","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"95b522232ea59b3ec56dcb082cdf4e0641310e1b","datavalue":{"value":{"time":"+2018-01-22T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q680146$53ABDA10-4579-492E-BC61-A6E207177771","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"7dbeeb65e6dbb38ce5284b929df338e6f4d067d6","datavalue":{"value":"The authors deal with the problem of unit disk cover (UDC), i.e., given a set \\(P\\) of \\(n\\) points in the plane we search for the minimum number of disks of prescribed radius \\(r\\), which cover all points of \\(P\\). Firstly, the authors consider the UDC problem in the Euclidean norm and the radii of the disks is \\(1\\). They propose a \\(4\\)-approximation algorithm that runs in \\(O(n \\log n + n t(d))\\) time, where \\(t(d)\\) is the time for computing the distance between point and set. Using appropriate data structures the proposed algorithm can be implemented to run in \\(O(n \\log^2 n)\\) time and use \\(O(n)\\) space. Next, the authors improve the time complexity of the algorithm by the use of sweep-line and obtain an algorithm that runs in \\(O(n \\log n)\\) time and uses the \\(O(n)\\) space. Then, they extend the algorithm from Euclidean metric to the \\(L_t\\)-norm for \\(t \\geq 1\\). For various values of \\(t\\) the authors obtain different approximation algorithms. For \\(t \\in [1, 2]\\) they obtain a \\(5\\)-approximation algorithm, for \\(t \\geq 2\\) a \\(6\\)-approximation algorithm, whereas for \\(t = \\infty\\) they obtain a \\(2\\)-approximation algorithm. All the algorithms run in \\(O(n \\log n)\\) time. Finally, the authors consider a unit ball cover, i.e., given a set \\(P\\) of \\(n\\) points in 3D space we search for the minimum number of unit balls which cover all points of \\(P\\). They show how to extend the 2D version of the UDC algorithm to the 3D case. The proposed algorithm is a \\(12\\)-approximation algorithms that runs in \\(O(n \\log n)\\) time.","type":"string"},"datatype":"string"},"type":"statement","id":"Q680146$5251629B-737C-4667-91DE-2EEA611055A5","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"2ce72165d993b0b8ed97728d731d2db2473b9554","datavalue":{"value":"65D18","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q680146$3C4412E9-F2D2-4245-9732-E11C320D2663","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"355ea56a4f84d7973d94c70a8b1f92966ec83542","datavalue":{"value":"65Y20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q680146$C395C596-5124-45F2-A49A-482404A62095","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"9838ddfecb740b9131d2943f6bb1145ed7cd88ce","datavalue":{"value":"6828435","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q680146$2D33F360-D5CB-43A6-BE2B-9DFEA77A1842","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"09c90441390386d38d4efb13fe40fd784653ab1b","datavalue":{"value":"unit disk cover","type":"string"},"datatype":"string"},"type":"statement","id":"Q680146$4B891CFE-B6F7-45B4-86E8-278166CAA3E8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"00bbdad754e80d461771bb62f0bd933570733da9","datavalue":{"value":"unit ball cover","type":"string"},"datatype":"string"},"type":"statement","id":"Q680146$7BCD9F06-03FF-4520-AAB2-18353A6D7BC0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cc4837877785b4675d8ac1c6d4c911bcaf794e13","datavalue":{"value":"approximation algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q680146$6BAFD5D8-BFA0-4327-90CB-CCD76FFBAFDA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c5f8382ba04f9f05f645b4d0e4b9ea28f0619583","datavalue":{"value":"complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q680146$51F45368-1A60-493F-8E32-72CB8BDDDC63","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"4e8aff2b8e51ed9533d593cc755cbfae6f7c82e5","datavalue":{"value":{"entity-type":"item","numeric-id":305012,"id":"Q305012"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q680146$516FB098-3F0E-47B0-8271-DB33C0B16CF3","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":"Q680146$3DAF9F5E-A67C-4346-AA9C-3961815595D2","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"b0674ee87e07b59a14fc981887fa65cf2b744bd1","datavalue":{"value":"https://doi.org/10.1016/j.comgeo.2016.04.002","type":"string"},"datatype":"url"},"type":"statement","id":"Q680146$1B46349F-D8FF-418A-9FFB-A03ACAA341DB","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"fb77cc68a476fd62edef9eedd7b971983bf8494c","datavalue":{"value":"W2341114440","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q680146$7D011DC4-31B9-497B-944D-036A59C41454","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"33ce89c39eded45d5a7a9d9cb06ace1eda77c8a8","datavalue":{"value":{"entity-type":"item","numeric-id":3911409,"id":"Q3911409"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q680146$15A018F8-5FDF-47B5-B62F-5ECF338232B9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"83749458eedbcd9ca976877a83efacc450ae6cfd","datavalue":{"value":{"entity-type":"item","numeric-id":1906049,"id":"Q1906049"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q680146$9E0DB413-3B9F-453C-BFD8-AD1E7E2F0CB7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"472923edd2b0a68c9a6e304ecec1422c153fe742","datavalue":{"value":{"entity-type":"item","numeric-id":420575,"id":"Q420575"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q680146$0087A659-39F1-4A6D-970D-C613D1F5DE6B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"56431db8c58e4e635497634670951f53dd4090e1","datavalue":{"value":{"entity-type":"item","numeric-id":1825634,"id":"Q1825634"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q680146$9466B06D-FFA8-48C8-B329-E2E3C55FE2C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"307fb49f6fe2fb59c207608c4367a76916d437d2","datavalue":{"value":{"entity-type":"item","numeric-id":1157170,"id":"Q1157170"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q680146$CDCDD2AC-C482-4900-B8AF-5ADCFF66C907","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c4630925004f8ac93be2ded2ce3a3f5591b82bd5","datavalue":{"value":{"entity-type":"item","numeric-id":5434450,"id":"Q5434450"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q680146$B1FF5820-59AB-4AAB-AA96-DBC4190F5DE8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"da58a63b612907758158a14d7d34c8b31394855c","datavalue":{"value":{"entity-type":"item","numeric-id":1183467,"id":"Q1183467"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q680146$BFD12048-3477-42EF-9EB9-215BF1E9F77F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"81078a7460abf00d8505be96a597e8d07c36cc68","datavalue":{"value":{"entity-type":"item","numeric-id":3771608,"id":"Q3771608"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q680146$6759AD8B-8546-4150-B497-668312FAFBEE","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"fa68a82caeb4fe81525ae9aaee48cb24cc20e8af","datavalue":{"value":"10.1016/J.COMGEO.2016.04.002","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q680146$2B2667DE-E24D-4282-B509-C76ADE0BAC18","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1e670ce39d916bc2953302559d5a1d3b16649e06","datavalue":{"value":{"entity-type":"item","numeric-id":491638,"id":"Q491638"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"14580c95afa95ad72109aaf8e4c88a3e3fa0fbd8","datavalue":{"value":{"amount":"+0.8774786591529846","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":"Q680146$DCF020EB-0827-4E8C-BC62-C05234D1523F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"790d934b2b5fb18d15db6a4c04825b6623d9bf39","datavalue":{"value":{"entity-type":"item","numeric-id":3078392,"id":"Q3078392"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"94f74da720d9c0b84aac8c30b13445525538fe3c","datavalue":{"value":{"amount":"+0.8662111163139343","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":"Q680146$BE199FB9-C019-4F4B-B0B0-69BA1F07D18E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"de8278143b84ae40d61223ed14994ac01425ae68","datavalue":{"value":{"entity-type":"item","numeric-id":5300002,"id":"Q5300002"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"34bfa3fef1d5110f6f90af5d094362bc2da23561","datavalue":{"value":{"amount":"+0.8655744791030884","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":"Q680146$46B37871-8350-483F-AA5B-E4872D935A96","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f04eee76904687df1df70fedfbd209c90ac166fa","datavalue":{"value":{"entity-type":"item","numeric-id":3560062,"id":"Q3560062"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2b4af49a927dd6e559591573ec70540478789c71","datavalue":{"value":{"amount":"+0.8369462490081787","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":"Q680146$08C3C106-E44D-49B2-B2A0-FAFE3E744B53","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f7232870c273a02d89659dc444e5dfa95487b262","datavalue":{"value":{"entity-type":"item","numeric-id":3652190,"id":"Q3652190"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"41dfd5b785993bf8ca3f6842bd5e5c3b471b7b93","datavalue":{"value":{"amount":"+0.8276352286338806","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":"Q680146$2578A67F-AB31-4B17-AF60-0C24D7AEBBEF","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Approximation algorithms for the unit disk cover problem in 2D and 3D","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Approximation_algorithms_for_the_unit_disk_cover_problem_in_2D_and_3D"}}}}}