{"entities":{"Q1421029":{"pageid":1431769,"ns":120,"title":"Item:Q1421029","lastrevid":67405428,"modified":"2026-04-12T17:24:42Z","type":"item","id":"Q1421029","labels":{"en":{"language":"en","value":"On simplifying dot maps."}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 2031377"}},"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":"Q1421029$A798CCB9-32B7-4AAD-828D-CD4A9668A872","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"532bf4baafdc9329477223b253d3ee8c38223e6b","datavalue":{"value":{"text":"On simplifying dot maps.","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1421029$4D6E12EC-7EE5-4DAA-B341-B0D417A86390","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"9887941106945c89abc5ffb2ddd1c11d9ab90067","datavalue":{"value":"1041.65023","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1421029$86164C12-9F88-41AE-B208-4F084D669320","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"22f6b12f56f2aa9fd0d8aea816f351f53d73fd4f","datavalue":{"value":{"entity-type":"item","numeric-id":223040,"id":"Q223040"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1421029$14132BC0-3FDF-4017-B6B9-1092DFC763E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"5ad270bb876f3a5e6f503d45a05fd7b45a710a3d","datavalue":{"value":{"entity-type":"item","numeric-id":223041,"id":"Q223041"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1421029$9685496F-BFBA-405C-A3C6-2F945BE2CE3C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f238d7848d0d2745ced3187f54790200083b50d3","datavalue":{"value":{"entity-type":"item","numeric-id":802872,"id":"Q802872"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1421029$4F3F89FB-08C8-4D79-9BF1-67C232DF513C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"fe51ab34fca76d52c385a1ca93b7dc29b1c6d1a2","datavalue":{"value":{"entity-type":"item","numeric-id":1175645,"id":"Q1175645"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1421029$66184946-F677-41AB-9D96-5574CC127604","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":"Q1421029$AB86B9ED-26DD-469C-B530-A59760947245","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"8e953e40a98762a68bef74ffc60d05e25f086206","datavalue":{"value":{"time":"+2004-01-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":"Q1421029$C786BFFC-CA62-4629-B200-CC104C93E750","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"05e4cc590cad8ab901be106e97b910d70874d2a2","datavalue":{"value":"Dot maps are a known method to visualize density functions over an area.. Given a set \\(P\\) in the plane, the authors want to compute a smaller set \\(Q\\) of points whose distribution approximates the distribution of the set \\(P\\). The known concept of \\(\\varepsilon\\)-approximations is used for a formal approach. Efficient algorithms for computing the approximation error of a set \\(Q\\) of \\(m\\) points with respect to a set \\(P\\) of more points for certain families of ranges, namely unit squares, arbitrary squares, and arbitrary rectangles are presented.   For instance, if the family of ranges is the family of all possible unit squares, then it is possible to compute the approximation error of \\(Q\\) with respect to \\(P\\) in \\(O(\\log n)\\) time. For the family of all possible rectangles an \\(O(mn\\log n)\\)-time-algorithmus is given. The paper contains some experimental results about the evaluation of some heuristics for good approximations given in the last chapter. An open problem is the following: The authors suspect that computing the best approximation of a given size with respect to a given set \\(P\\) is \\(NP\\)-hard . Further the problem of giving some points of the set \\(P\\) a higher weight for a bigger chance to be present in \\(Q\\) is discussed.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1421029$D685DDA2-0749-486C-B869-BAFD81CE1C87","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"f97401dc38cdab90e116741461a88db9a2626407","datavalue":{"value":{"entity-type":"item","numeric-id":701798,"id":"Q701798"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1421029$D179A26D-8575-490C-9625-126360A47F0E","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"2ce72165d993b0b8ed97728d731d2db2473b9554","datavalue":{"value":"65D18","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1421029$B64D5CE4-8763-422F-A850-686E57D401B7","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"572947134a6904befde544c2db67b89edaa1d13a","datavalue":{"value":"2031377","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1421029$D1C5EF21-092E-4946-BA7F-8281943BE1F0","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"834fb48bd46aa18c210bb72501ba9f134f206f44","datavalue":{"value":"\\(\\varepsilon\\)-approximations","type":"string"},"datatype":"string"},"type":"statement","id":"Q1421029$2C90D422-3B39-4A15-9332-A8EBAC95FF14","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bf92368602e9299f2a65cb3b2ddac9f3726dee9b","datavalue":{"value":"dot maps","type":"string"},"datatype":"string"},"type":"statement","id":"Q1421029$0EE74BCF-A68A-47EE-8C5E-F3DFC6667FA4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1f30f01baa0dbe102ed14d61f6acd511c378aa58","datavalue":{"value":"discrepancy","type":"string"},"datatype":"string"},"type":"statement","id":"Q1421029$8743BCA0-222C-46FF-975E-175B1E9B06A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fbf06a3bb780dfd41b625a200f022a01b57481b6","datavalue":{"value":"visualization","type":"string"},"datatype":"string"},"type":"statement","id":"Q1421029$4F60E290-523D-44F1-B873-DB2CF656943A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d84aed947d32e1fb3152a3196e6debf9578a5567","datavalue":{"value":"density function","type":"string"},"datatype":"string"},"type":"statement","id":"Q1421029$91AEAB49-2DE6-4321-A17E-AD0345C6C910","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"48ddf43eca498c7e7087cd696beb82ea63925320","datavalue":{"value":"algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1421029$BF0A917A-1028-4870-B59C-A00EF217DE70","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1d74cb5419439f42eb1ba8891c8722bd3702922d","datavalue":{"value":"numerical examples","type":"string"},"datatype":"string"},"type":"statement","id":"Q1421029$F34B054F-D894-4595-9C23-96A2DB0D3388","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":"Q1421029$9F0ED361-C9CE-453C-9668-3497D4721BC1","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"68b0e4ab4ecd1c8ebfb2300ecf0011733b646b7b","datavalue":{"value":"https://doi.org/10.1016/j.comgeo.2003.07.005","type":"string"},"datatype":"url"},"type":"statement","id":"Q1421029$FB3367B0-0D7B-4DEF-9450-DC5E82AEF93F","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"bda1bde2554feaa74a9f4a0e2f0eb23e1512be26","datavalue":{"value":"W2099217816","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1421029$FE4AB222-46B6-4063-A396-B65E49BAEDDA","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"73adef94b8d6b2e464abdd8ad288e7bd9624427d","datavalue":{"value":{"entity-type":"item","numeric-id":4401021,"id":"Q4401021"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1421029$68C800E3-789B-4843-AF39-7198D21FB948","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":"Q1421029$527D4341-6568-4E70-9B5A-FD6DDF447983","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8b57c04ab47cc7a76b16d5be6cd512c57dbf7d88","datavalue":{"value":{"entity-type":"item","numeric-id":1873153,"id":"Q1873153"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1421029$D1C99876-BB68-4E07-9108-A1AF189E41B9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b1de42504ce667266ce591b8331d2abd083a0c4f","datavalue":{"value":{"entity-type":"item","numeric-id":4515159,"id":"Q4515159"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1421029$E66E5E5E-2459-4B90-B56B-2489A506EF43","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cd84b644690ea1604632b6aa4e91108f5644dbdc","datavalue":{"value":{"entity-type":"item","numeric-id":1924382,"id":"Q1924382"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1421029$4853B411-8D76-46D4-8301-8CA87C9EFFCC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f231b7156d719d1aa7cc88dd69bbe7bc78a7850a","datavalue":{"value":{"entity-type":"item","numeric-id":5361591,"id":"Q5361591"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1421029$662C7382-D4DD-4A46-93D3-FBDAF6702220","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"db54ce2565b65c0cdede599ad503ee5a657feb5e","datavalue":{"value":{"entity-type":"item","numeric-id":1773216,"id":"Q1773216"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1421029$AD925A09-1994-4BEC-BED9-9E9B13A2027B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7faae9af4da6c660435a45fe90739b231673546d","datavalue":{"value":{"entity-type":"item","numeric-id":3985807,"id":"Q3985807"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1421029$799A98EF-1DF8-4E47-9EFA-33A4812C7653","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e55670eeffeb14e6ce51166fb8470acff9c12ef5","datavalue":{"value":{"entity-type":"item","numeric-id":5660314,"id":"Q5660314"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1421029$5749E012-FCD0-4D8E-BB43-7FB52AFF41DA","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b13116a1f2e325aae71513292e44517c2e017f5c","datavalue":{"value":"10.1016/J.COMGEO.2003.07.005","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1421029$726B5799-C63A-42F0-BDD6-C3BB464B901F","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a74ee66a53eb4d7fa213b3f324a969efd4f8b85b","datavalue":{"value":{"entity-type":"item","numeric-id":3521939,"id":"Q3521939"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5c249aef667cd133af0dea09754e5ce2874115a6","datavalue":{"value":{"amount":"+0.7303688526153564","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":"Q1421029$CB9FB581-5FB5-4CE6-A9BC-0CF0639097A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b4f5b3a5eba39f152b374553b2a1543c6bc94c86","datavalue":{"value":{"entity-type":"item","numeric-id":5232487,"id":"Q5232487"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8edde1ba9aae62dd13812b38b0cc62d5a58a1ee5","datavalue":{"value":{"amount":"+0.7283943891525269","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":"Q1421029$C119DD3F-ABFB-46E8-A1E0-72A9F4C39C31","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d4e481fe11ee802ae2ba4b4c42c4b299966ac301","datavalue":{"value":{"entity-type":"item","numeric-id":1957642,"id":"Q1957642"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a9923c916d9412e75a31b27a6405bae0554fee55","datavalue":{"value":{"amount":"+0.724824070930481","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":"Q1421029$A90D64DE-F4D6-4D4E-9140-08A2E2B25930","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"953689be6027bbf06b4eb2de2325cf5b55c062b2","datavalue":{"value":{"entity-type":"item","numeric-id":5449575,"id":"Q5449575"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d378e5c2a1e7ca8c579020c317589194d83560ea","datavalue":{"value":{"amount":"+0.7201738357543945","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":"Q1421029$A02AB702-DB0E-473D-9A9D-99C498EBB592","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"53ea39a7d8dc1a8bc3f80d21e91e954e84db103d","datavalue":{"value":{"entity-type":"item","numeric-id":2943553,"id":"Q2943553"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a8d5946f409e72f66df06cbf78d8118d1e33a2a8","datavalue":{"value":{"amount":"+0.7192444801330566","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":"Q1421029$778E23A6-F0E6-49CD-BB2F-C9DEAA26DD61","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On simplifying dot maps.","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_simplifying_dot_maps."}}}}}