{"entities":{"Q441888":{"pageid":443655,"ns":120,"title":"Item:Q441888","lastrevid":61850241,"modified":"2026-04-11T02:05:33Z","type":"item","id":"Q441888","labels":{"en":{"language":"en","value":"The planar \\(k\\)-means problem is NP-hard"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6064162"}},"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":"Q441888$542F4695-FB8E-4C5B-ABB8-B6EC4AF0A257","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"276374d5be4db0d625475bb7722bda335f239deb","datavalue":{"value":{"text":"The planar \\(k\\)-means problem is NP-hard","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q441888$459D1F34-F748-453D-8E73-A091B59B1823","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"e6a646df35279d6712284742b24bd6e3faf89d6e","datavalue":{"value":"1260.68158","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q441888$F55C00B7-D019-47EA-AF76-E62BAEF6AADB","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"255779f34e1857f1e1d5d34372c6a4a28e1cfdd7","datavalue":{"value":{"entity-type":"item","numeric-id":371192,"id":"Q371192"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q441888$51E32431-F91E-4D82-8B12-1DA959111CC9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"7cb4ba24b3df4343ef3971c6723e86d00cd22d4a","datavalue":{"value":{"entity-type":"item","numeric-id":385513,"id":"Q385513"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q441888$BE6C5346-16CE-40E6-843D-2A3763301596","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"cce85b4d0d7087c3d8e248a5cdb4c3b856fdb3b1","datavalue":{"value":{"entity-type":"item","numeric-id":590541,"id":"Q590541"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q441888$E528AD4C-A599-48E1-8305-3B38A9D7D3A9","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q441888$92307427-5753-4E14-9F75-6FEDEC1EFA4F","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"44f3e8b83609cf4e3eda11fc160cf4b0b2caf1b7","datavalue":{"value":{"time":"+2012-08-08T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q441888$53D61B81-4F3F-4743-905E-62C78FC26122","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"09a7a92c543341bcaee384f3d89d0bfee6568a59","datavalue":{"value":"The authors prove the NP-hardness of the decision problem associated with the following optimization problem: given a set of points in the plane and a positive integer \\(k\\), find a set of \\(k\\) centres so as to minimize the sum of the distances between each point and its nearest centre. Here the distance between two points is defined as the square of their Euclidean distance. In a generalization of this problem, the \\(k\\)-means problem, the input points are allowed to be in a Euclidean space with arbitrary dimension. The \\(k\\)-means problem is a very natural clustering problem and it has been studied immensely in machine learning and algorithm communities (see the references in the paper). It had been known that the general problem is NP-hard, and that if both the dimension and the number of centres are fixed, then a polynomial time algorithm exists. This paper resolves the case in which the dimension is fixed but the number of centres is part of the input. The proof uses a complicated reduction from the planar 3-SAT problem to the planar \\(k\\)-means problem.","type":"string"},"datatype":"string"},"type":"statement","id":"Q441888$EEA6BA1B-6A44-421C-9420-C6FD6A5AF5B4","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"5bdbd2841f25e28abb13d3321659eedc18bcc203","datavalue":{"value":{"entity-type":"item","numeric-id":329280,"id":"Q329280"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q441888$F002B4B0-1832-4808-8661-DF20DE126E87","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q441888$4836F30A-25C2-4B15-867D-38786FBE3E79","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"159426a5937e62cfbbcc198dd4848ab52d6e715e","datavalue":{"value":"68U05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q441888$39D6C036-5B9D-43AB-B303-9AF0637BFC5C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"357c7c34a1a90d83243f17011b7aa90788d1792d","datavalue":{"value":"05C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q441888$8CB35782-FE76-4A1E-99BC-D3648C226B01","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"9904bcace9a2bb62fe7038b8daee3e5550df6a43","datavalue":{"value":"6064162","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q441888$02B644CF-6C01-43AE-98E3-FD185687C70A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e9c4e650abc856b5f51d0b5123c5930fad01c53f","datavalue":{"value":"clustering","type":"string"},"datatype":"string"},"type":"statement","id":"Q441888$4C34E60A-0D82-4C69-B407-927F0E97B4E8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0d43cc73d1b6ab5a92fa9be6cbbe06479ffe1fe2","datavalue":{"value":"\\(k\\)-means","type":"string"},"datatype":"string"},"type":"statement","id":"Q441888$B6D70FD7-A980-4349-B4A8-159978B0F3F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a7718c99048f5049d164853f332332674c8072fb","datavalue":{"value":"planar 3-SAT","type":"string"},"datatype":"string"},"type":"statement","id":"Q441888$C7447CD6-E10C-44B0-A3A4-DA76543E5A47","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c7d5e4886aa4290eca104cd0d1da319d8b4d34c4","datavalue":{"value":"NP-hardness","type":"string"},"datatype":"string"},"type":"statement","id":"Q441888$D15B52E1-3CBA-418B-B6B2-E0EAC33E3C85","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"05011155899c0462ad1ad3e4f60fc5d3a6a2c63c","datavalue":{"value":{"entity-type":"item","numeric-id":33424,"id":"Q33424"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q441888$66EE57F6-DE25-4296-85F6-BC65705E2CAD","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":"Q441888$8C56FE14-91C0-4648-9760-F1799CB409CC","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"205964cba80ae0a9a943adb1a2d8675416b91e69","datavalue":{"value":"https://doi.org/10.1016/j.tcs.2010.05.034","type":"string"},"datatype":"url"},"type":"statement","id":"Q441888$A4243257-8B2A-4EF1-B832-30EF2589B589","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"3efd39fde460a44c3efcaf8c90c7ac2bfbb35365","datavalue":{"value":"W2160039585","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q441888$33BF4884-5503-494C-B729-5B0E6B107A0A","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"5245e1c4ddc08a89d405e2a427a1ba7560a108fb","datavalue":{"value":{"entity-type":"item","numeric-id":5897773,"id":"Q5897773"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q441888$C810F86A-1548-46F8-94B3-BECA972151C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"53d96a13635fd4c783d8cab8cc984916f43c6655","datavalue":{"value":{"entity-type":"item","numeric-id":1009338,"id":"Q1009338"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q441888$A4AB83B8-142F-4D75-BA87-353DFA64FCEE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2080d98190420d9cfa9ba25cd5869a48c6addc2d","datavalue":{"value":{"entity-type":"item","numeric-id":3601533,"id":"Q3601533"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q441888$CC1779C5-1A6A-4688-BBB5-0AACF56A3A82","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bbd1dbeb6a375d1aab8652053df32dc599fef3b9","datavalue":{"value":{"entity-type":"item","numeric-id":3558022,"id":"Q3558022"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q441888$AFB513AE-8BB2-450E-85B3-3EF09BDD5855","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"70b65ffee2151d7792e5d0fd35e6c89d1d634cb1","datavalue":{"value":{"entity-type":"item","numeric-id":2934696,"id":"Q2934696"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q441888$CA7F4D9A-7658-432C-8AE3-CBA489340965","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3a5926a064782b196fce41c7129090bcbba862c5","datavalue":{"value":{"entity-type":"item","numeric-id":3581243,"id":"Q3581243"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q441888$60CAD658-06BC-497D-A493-58DC8DF126A7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"095d8d8ed52a33c68eaa5da6e143987042dc6d65","datavalue":{"value":{"entity-type":"item","numeric-id":703073,"id":"Q703073"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q441888$970BC62C-FB54-4BCD-95F0-A92B01DDA759","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1decbb876fad627b784b0ee6119dd94458061fb3","datavalue":{"value":{"entity-type":"item","numeric-id":3512466,"id":"Q3512466"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q441888$A2172EA9-908D-4BE1-999E-A91A79A519AC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4845a6f73c80dba6a91ad75f5e0a84c08aae8965","datavalue":{"value":{"entity-type":"item","numeric-id":2921753,"id":"Q2921753"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q441888$DE05FADA-83D2-4AB7-A3B4-23B634770931","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e0d4d8523a922703cf50956160d768d1dfc61c54","datavalue":{"value":{"entity-type":"item","numeric-id":598232,"id":"Q598232"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q441888$4346DD80-67C4-4B5C-A90F-9F2E36B6DAC7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"176f92be0a5c8084cbea32a162c15c6e5a582bd9","datavalue":{"value":{"entity-type":"item","numeric-id":3936195,"id":"Q3936195"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q441888$EDAFA857-1F55-4259-9B3D-E95F4675AC9E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f8e2f6c00ec529074a370fb6498a18761aa02104","datavalue":{"value":{"entity-type":"item","numeric-id":4740474,"id":"Q4740474"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q441888$3516226F-2997-4F54-A149-417B5A60D2CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"92a3e9debcab806c14aff8e499e51be47c884542","datavalue":{"value":{"entity-type":"item","numeric-id":3745276,"id":"Q3745276"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q441888$5120CEEA-76D0-498F-BAE4-9C0CB142B609","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a5c3ddd4007917f647a575807ea575e87e66138e","datavalue":{"value":{"entity-type":"item","numeric-id":3318110,"id":"Q3318110"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q441888$F122D07A-CF44-4EDF-A5AB-A9DAEDA9132C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5543e119650811c9648ae3bc0f721e47a5bddc1f","datavalue":{"value":{"entity-type":"item","numeric-id":5395696,"id":"Q5395696"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q441888$F721DFEC-F232-4634-A023-1D8CCD057186","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dcc67d47bf3c27fbeab166391b3b3e9d154ed32f","datavalue":{"value":{"entity-type":"item","numeric-id":3904539,"id":"Q3904539"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q441888$FCB6ED23-05CB-432E-B9E3-5FCADFE03439","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8b009c3f339c120f27b57102655d9d06a33d96db","datavalue":{"value":{"entity-type":"item","numeric-id":5370732,"id":"Q5370732"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q441888$C54C9889-3CF8-4217-90A2-91FD331D1581","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"33411c2e7b5fd6d03e93d7e124b8c840cc68e273","datavalue":{"value":"10.1016/J.TCS.2010.05.034","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q441888$80B9DADE-1F65-4EDC-B314-5961DEC6C80B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1501cc61ba40b3b1afafad4310781b65d73df38d","datavalue":{"value":{"entity-type":"item","numeric-id":3605504,"id":"Q3605504"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"44f235408175c51c974a7f7d035cc0c88d29a4bd","datavalue":{"value":{"amount":"+0.9378864765167236","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":"Q441888$F66DC6C5-A2F7-4ED0-BCDF-957D5F94A70C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"af95b60b02bf2fd7d1b92d258af87a969fe34d62","datavalue":{"value":{"entity-type":"item","numeric-id":906118,"id":"Q906118"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c01ba26a4b612d88e499c6b86df14641bc6d3271","datavalue":{"value":{"amount":"+0.8311229348182678","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":"Q441888$3929D9CF-7D0E-4BC3-A4D1-49E65290CE70","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ab75bb6c8f95a6248ca276c946bf25822e0071c7","datavalue":{"value":{"entity-type":"item","numeric-id":506167,"id":"Q506167"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"98e4061e7ae0daf6007d55601381df097131ff77","datavalue":{"value":{"amount":"+0.8237833380699158","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":"Q441888$43D01D63-8C93-42F0-A2BF-81D8AF182203","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1c42ff04309793b1ec1cf7fd06d206816fbcdd5e","datavalue":{"value":{"entity-type":"item","numeric-id":5368726,"id":"Q5368726"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"95658985ff8f41ee4aad701af65ba4c31eea2c62","datavalue":{"value":{"amount":"+0.8149650692939758","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":"Q441888$2B0254B9-7B70-40E5-AC06-419FB6025784","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"34a1569dee401f06fd6e328fa54a4c967c7b1558","datavalue":{"value":{"entity-type":"item","numeric-id":1009338,"id":"Q1009338"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a47e437086678ce4947db6da962543b240dbdf2c","datavalue":{"value":{"amount":"+0.8094337582588196","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":"Q441888$5119EDD3-499A-4290-99FF-BAD607C60470","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The planar \\(k\\)-means problem is NP-hard","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_planar_%5C(k%5C)-means_problem_is_NP-hard"}}}}}