{"entities":{"Q1116694":{"pageid":1127443,"ns":120,"title":"Item:Q1116694","lastrevid":69680823,"modified":"2026-04-13T08:40:22Z","type":"item","id":"Q1116694","labels":{"en":{"language":"en","value":"Polynomial algorithms for restricted Euclidean p-centre problems"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4090790"}},"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":"Q1116694$960C075B-9FBF-4FEF-B5FA-83161031C613","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b39267a79c1fe2d33049dbddad908b78edc659e1","datavalue":{"value":{"text":"Polynomial algorithms for restricted Euclidean p-centre problems","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1116694$962BF549-9704-4047-A685-5496B32FCC98","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"8593bccf45fbccc4ee1d49e6e0161441e90f581e","datavalue":{"value":"0666.68036","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1116694$7DB76AD3-917F-4289-BFAF-5C45A97B8271","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"d4aecc444018d4cf51868afd615c8f1ac2480e0d","datavalue":{"value":"10.1016/0166-218X(89)90032-2","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1116694$E3D4C16F-244B-473C-B71F-14E271EA91AE","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"90fb1cb81efcd29990b1a2e60517676894b5d85b","datavalue":{"value":{"entity-type":"item","numeric-id":1116692,"id":"Q1116692"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116694$CEF49117-E705-43DA-B562-3CB56FDD11DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"1aef8e414282f2cb45fbc1671e48799b4446488b","datavalue":{"value":{"entity-type":"item","numeric-id":1116693,"id":"Q1116693"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116694$55493179-2D7E-4C75-818B-F666D716DEAD","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116694$D8A2C829-B42A-4327-A3FE-1377CBCE8C34","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7211ad5ca16eb0d22cd0051fff3d0f3af254ceb6","datavalue":{"value":{"time":"+1989-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1116694$0AC2E727-BC66-4C03-A3A8-1A8C1BC0A424","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"5170e482d06c7d3d12b7a12343f3104cf7e82413","datavalue":{"value":"Given n demand points in the plane, the p-centre problem is to locate p supply points so as to minimize the maximum distance from a demand point to its nearest supply point. Megiddo and Supowit have recently shown [\\textit{N. Megiddo} and \\textit{K. J. Supovit}, SIAM J. Comput. 13, 182-196 (1984; Zbl 0534.68032)] that not only is this problem NP-hard, but even finding a close approximate solution to the problem is NP-hard. In this paper we present a polynomial time algorithm for the Euclidean p-centre problem when the demand points are restricted to lie on a fixed number of parallel lines.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1116694$F242EEEB-0A46-493C-851A-4DBD2EE64F14","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1116694$A7CB0282-DE51-44C7-BB6F-C7AEF9A43BD8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fa4669cf5eaa224b5d3554d9705827ca09f43afb","datavalue":{"value":"52A37","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1116694$BDA79F38-EC84-446A-BD7D-512EF269A092","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"6be8d77a1a32d1c84309f901f105630d3a571775","datavalue":{"value":"4090790","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1116694$BD90F186-DE65-4D7E-B467-87B27BF99D5A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"551d108313cfab3a77b395a647aede7021169ebd","datavalue":{"value":"computational geometry","type":"string"},"datatype":"string"},"type":"statement","id":"Q1116694$7AF08411-31D7-4BEE-8A52-2D0646D30F00","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b5a461a454d18cff97479165dab43cb6d0193d9e","datavalue":{"value":"p-centre problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1116694$BBEB1942-783A-4B04-9E43-C2CDE57262D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8f12ea105addea4e52f9511695748975bd61a49c","datavalue":{"value":"NP-hard","type":"string"},"datatype":"string"},"type":"statement","id":"Q1116694$2DED0D96-C366-4B9F-B5E3-FD77A64E922D","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":"Q1116694$E64D2EE6-EA6F-42A6-9991-D8875D2EBC7F","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"381849b10bf1323497130a4ed2f70969666a5760","datavalue":{"value":{"entity-type":"item","numeric-id":4747524,"id":"Q4747524"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116694$D0A0C2B6-20C7-4E43-A278-472F1D13644F","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":"Q1116694$FF29902B-6C85-49B0-B464-C5BEAE8AC309","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"713e82ac9e8a1be90ecdf20e49c91764c51169c3","datavalue":{"value":{"entity-type":"item","numeric-id":3906433,"id":"Q3906433"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116694$6F470C30-B05A-4763-84E7-D9554685B00A","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"fd3bd0e93a9510d76618ff03c3d869756aa1f5c2","datavalue":{"value":"https://doi.org/10.1016/0166-218x(89)90032-2","type":"string"},"datatype":"url"},"type":"statement","id":"Q1116694$A3F216D3-5015-4337-93EF-F7444408392A","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"fd88269492bcd2f102d229b32ea905fd392478ca","datavalue":{"value":"W1970240082","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1116694$405AD999-AE94-4163-BEAC-B97A447AD86B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"acfd215f31be8e71adb12d6e8c8c0f0e3cf8e221","datavalue":{"value":{"entity-type":"item","numeric-id":3335476,"id":"Q3335476"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ee743c74259e0b8c91edb54640d8dd7660ade35e","datavalue":{"value":{"amount":"+0.8572289347648621","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":"Q1116694$32CA14E4-FE3C-4BCA-A4A9-6FAB9FC9EFAD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b44046363a7cae67525c3c2a97119b31369776d6","datavalue":{"value":{"entity-type":"item","numeric-id":4723543,"id":"Q4723543"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"52fdb52daa99cd53321b17f612ad69db56e94150","datavalue":{"value":{"amount":"+0.8460343480110168","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":"Q1116694$635C4FFD-1B1D-4718-B449-381B0D651CD7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"72e3482fcdae553097fff6f371265ecf9081e1d6","datavalue":{"value":{"entity-type":"item","numeric-id":3318110,"id":"Q3318110"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a87f1eb2ea161471ec7cb9a6e5ed859b958e041c","datavalue":{"value":{"amount":"+0.8362753987312317","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":"Q1116694$F65C558A-125F-45F6-88B1-F07F770D233B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"674fe234f9f11745873c4455199e92a087bd0a55","datavalue":{"value":{"entity-type":"item","numeric-id":3748028,"id":"Q3748028"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"addc60b48afbb00d1dd2afc10c77da86df4c6ee3","datavalue":{"value":{"amount":"+0.8311061263084412","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":"Q1116694$8B76552C-17E2-4A02-BE04-4FE405BA519C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4e9d6636cf8bc7c5c3788647d73dc0ae3f222459","datavalue":{"value":{"entity-type":"item","numeric-id":1207325,"id":"Q1207325"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ac85b6bf2ac5fa52166b167f2aa085b4e76e7b01","datavalue":{"value":{"amount":"+0.8300489187240601","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":"Q1116694$69386B9A-87F8-4A6F-858F-B8F0178C8F7A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Polynomial algorithms for restricted Euclidean p-centre problems","badges":[]}}}}}