{"entities":{"Q1122367":{"pageid":1133116,"ns":120,"title":"Item:Q1122367","lastrevid":49288870,"modified":"2026-01-06T22:06:25Z","type":"item","id":"Q1122367","labels":{"en":{"language":"en","value":"A study on two geometric location problems"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4106314"}},"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":"Q1122367$08C84FBD-CAC5-4618-9450-EB5DAB2D903B","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"7933b4ada78df26aa50a91b0ae3a13658f98ee55","datavalue":{"value":{"text":"A study on two geometric location problems","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1122367$ECCFFCDA-2794-4B70-A714-FF065045595D","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c7fdf45847dcc1bdee80f1667378167799595e80","datavalue":{"value":"0675.68071","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1122367$07516B26-ADFA-4F6F-98DD-B3A67C711ACB","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"4d7940da19e6b6f94d60695533731c81f0e3a6c8","datavalue":{"value":"10.1016/0020-0190(88)90174-3","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1122367$BCF8DDF8-96B3-431B-B89A-E290AAA600A1","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"aedf720352fcca932fab3523c4bbcafd7c4c7cdb","datavalue":{"value":{"entity-type":"item","numeric-id":1104176,"id":"Q1104176"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1122367$16A83F9C-375F-4AA1-B80C-CB1A4ADFC7E9","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52fa7d44b58d0511cb8993765bd916aef86052d8","datavalue":{"value":{"entity-type":"item","numeric-id":63092,"id":"Q63092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1122367$4ED85129-507C-4542-A679-96A2CFD9EF39","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"31a1937240ca4a323604b4728c31d242b5596d7c","datavalue":{"value":{"time":"+1988-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":"Q1122367$F84B646B-58CE-4DD4-86A0-D8AFBAC9B985","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"090799e8f5491750c11bbe58fe0c4e52ad4d6a5c","datavalue":{"value":"For a set S of points, two geometric location problems are considered in this paper: (A) For a positive real d, find a largest subset of S in which the distance between any two points is greater than d. (B) For a positive integer p, find a p-point subset of S in which the two closest points are farthest away. Both problems are considered in one- or two- dimensional Euclidean space, referred to as (A1), (A2), (B1), (B2). (A1) can be solved using sorting in O(n log n) time. A dynamic programming algorithm is given for solving (B1) in \\(O(pn+n \\log n)\\) time. (A1) and (B1) have lower bounds \\(\\Omega\\) (n log n). It is stated that problems (A2) and (B2) are polynomially equivalent, and the Maximum Independent Set for Circle Intersection Graphs (MISCIG) problem is polynomially reducible to problem (A2). It is proved that MISCIG is NP-complete. Thus, (A2) and (B2) are NP-hard.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1122367$1E2B9C57-B302-4BEC-94E6-7A2DEDB088D2","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"61f5e4db0e91212ef2106e3db512d71730a68751","datavalue":{"value":"68U99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1122367$35B2C432-D98B-429C-88F8-634D47DA3828","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1122367$D09EA4E1-A67A-4330-8C35-B344E773B5E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fa4669cf5eaa224b5d3554d9705827ca09f43afb","datavalue":{"value":"52A37","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1122367$9DF87E09-563C-4B0B-93E8-3B97A7AD1554","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"25fe30a6fe5285f54b3a7ea7d7e97ac0b640e4f9","datavalue":{"value":"68R99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1122367$4883FA38-9283-41CF-A4FE-FAB40ACCCF51","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c9493c15573ab30e73d7130068bcce70085fe338","datavalue":{"value":"4106314","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1122367$FDC23E74-1BB6-4B02-A0F2-DE0ABD05AC6F","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"551d108313cfab3a77b395a647aede7021169ebd","datavalue":{"value":"computational geometry","type":"string"},"datatype":"string"},"type":"statement","id":"Q1122367$434F7FF8-31A7-45CF-9AE4-121A504FDA1B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f1c87e82981d14041e23a8338535d244e4209e67","datavalue":{"value":"p-center","type":"string"},"datatype":"string"},"type":"statement","id":"Q1122367$A93AC1A2-BA1F-4B1C-9500-4B0F329F2E87","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0d82cfa81638332a8c825bcbbd9d7f7f9c0c45be","datavalue":{"value":"dynamic programming","type":"string"},"datatype":"string"},"type":"statement","id":"Q1122367$A4CBC76F-D53F-4B21-802A-27B016CE9F7E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8f12ea105addea4e52f9511695748975bd61a49c","datavalue":{"value":"NP-hard","type":"string"},"datatype":"string"},"type":"statement","id":"Q1122367$3E37958B-7208-4838-B5B4-786ABD138709","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":"Q1122367$AA57F253-5AE3-4D97-BADB-805BB7145A33","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"60dcce1a9b375851da0c567c5e08bc9ffe6d03f6","datavalue":{"value":"https://doi.org/10.1016/0020-0190(88)90174-3","type":"string"},"datatype":"url"},"type":"statement","id":"Q1122367$58EBAE13-8810-47FC-B6A0-8C1C3DDA1797","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"e3f1efd4bfc90a40a51bd500e1df2818df9a7b86","datavalue":{"value":"W1975512711","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1122367$09E6C9B7-2D6E-4934-B85B-7E18C30B127D","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1122367$19F789FF-103C-4F89-A4E5-7E14817E6DFF","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":"Q1122367$5E3C59B1-6D07-466E-96FB-C385A6C51718","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"694910451200ab7067ebbccacf142af3ac2a2369","datavalue":{"value":{"entity-type":"item","numeric-id":3992847,"id":"Q3992847"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1122367$10943C02-D2D3-499E-B424-5E6648152C96","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5a37d103b0980efe9ebda96b99dee36dba132e5b","datavalue":{"value":{"entity-type":"item","numeric-id":4176809,"id":"Q4176809"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1122367$1EC0577E-08C9-48F0-9D35-F2EC346CE523","rank":"normal"}],"P1643":[{"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":"c9143df6db54302bad5e5ac57dd91dd2d8314fa0","datavalue":{"value":{"amount":"+0.8125346302986145","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":"Q1122367$FF815F88-9940-432A-BD32-617DBE103CE6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a16fa5924bc900f5fdbea92d3ddf892f819844dc","datavalue":{"value":{"entity-type":"item","numeric-id":4728245,"id":"Q4728245"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6dc9ff931c7da0c99616bf122e44a25efe97f3be","datavalue":{"value":{"amount":"+0.7983908653259277","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":"Q1122367$8B903B7B-8AE0-409E-AC8A-912E2A4D360F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"380253360be57852c6b61ed256472abe38274f67","datavalue":{"value":{"entity-type":"item","numeric-id":3446821,"id":"Q3446821"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3c0472e659ed231d2764cfb58a19ca87d4876a54","datavalue":{"value":{"amount":"+0.7962294816970825","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":"Q1122367$B86A1DB9-A7E5-4191-81A8-7A8E0E8568C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e78221ec6b57ddbfb85ec8c4e1470fff34cdcc1c","datavalue":{"value":{"entity-type":"item","numeric-id":1099951,"id":"Q1099951"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"26a4ec9f13614c73b76ffc35fc62b138900ee915","datavalue":{"value":{"amount":"+0.7847709655761719","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":"Q1122367$675C4A40-64BB-45C2-A0D8-5C72FAFB01C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f744bd976115823cac92b5fbb4388959b8a27590","datavalue":{"value":{"entity-type":"item","numeric-id":5501300,"id":"Q5501300"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1e39c02bc65b3138380764b5c7392f0c49e3fff1","datavalue":{"value":{"amount":"+0.7847676873207092","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":"Q1122367$50D17D70-26F1-4348-BDED-8561FA4EA5E6","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1122367","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1122367"}}}}}