{"entities":{"Q1099951":{"pageid":1110703,"ns":120,"title":"Item:Q1099951","lastrevid":66328713,"modified":"2026-04-12T09:21:00Z","type":"item","id":"Q1099951","labels":{"en":{"language":"en","value":"Geometric complexity of some location problems"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4043243"}},"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":"Q1099951$33F74722-D1B4-4DD2-BCF0-B500B6E84644","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"1532898452e5ac8b859f7e75e10c9555208a31f7","datavalue":{"value":{"text":"Geometric complexity of some location problems","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1099951$28FF1431-DF83-4DBA-89AA-0A6D16412170","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"296afe83a622713d16ae90fb9b7ef4566b13292e","datavalue":{"value":"0639.68038","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1099951$EDCA6882-FEED-4FB5-8E4E-C06A32CD93B9","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b8e4979eb821af7e3de2a000ec7ff491d89b1d2f","datavalue":{"value":"10.1007/BF01840442","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1099951$2A591002-14B7-4D53-A3F7-3D1397C08592","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"83acb26c132edffe3503227fdedd09777c685939","datavalue":{"value":{"entity-type":"item","numeric-id":1060191,"id":"Q1060191"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099951$5E705CD7-EA5F-4653-B95A-50EB636F16F1","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"65c8fa095fb5e7de7a6818fd747ab8b39647de93","datavalue":{"value":{"entity-type":"item","numeric-id":96582,"id":"Q96582"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099951$D97D2070-AD61-4821-A161-A308F0C9031E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"63df7153432d81fa42019fcabb076c89649b0b5b","datavalue":{"value":{"time":"+1986-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":"Q1099951$61C4315D-7381-4B1A-A3D7-D4D611255A11","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"053349f1056fc4f9988d5d22c66d74fa640cb3de","datavalue":{"value":"Given a set of n demand points with weight \\(w_ i\\), \\(i=1,2,...,n\\), in the plane, we consider several geometric facility location problems. Specifically we study the complexity of the Euclidean 1-line center problem, discrete 1-point center problem and a competitive location problem. The Euclidean 1-line center problem is to locate a line which minimizes the maximum weighted distance from the line (or the center) to the demand points. The discrete 1-point center problem is to locate one of the demand points so as to minimize the maximum unweighted distance from the point to other demand points. The competitive location problem studied is to locate a new facility point to compete against an existing facility so that a certain objective function is optimized. An \\(\\Omega\\) (n log n) lower bound is proved for these problems under appropriate models of computation. Efficient algorithms for these problems that achieve the lower bound and other related problems are also given.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1099951$E9AE9D38-B04B-40FA-ADA3-CFB2DED7198D","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1099951$A22E9D15-0FC3-471A-9D8F-AF57286F44A6","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"878ef7accc6c44bdba9ed370aac0c514d8e7b7cf","datavalue":{"value":"4043243","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1099951$11BBE00D-E89F-4C07-83EE-A31892934692","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b185375f3f81c08c2c11b212eefb620ce1752ea2","datavalue":{"value":"maximum gap","type":"string"},"datatype":"string"},"type":"statement","id":"Q1099951$2ED7EF7B-612D-4338-9F96-03572BC3809A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"551d108313cfab3a77b395a647aede7021169ebd","datavalue":{"value":"computational geometry","type":"string"},"datatype":"string"},"type":"statement","id":"Q1099951$E8180827-E855-4844-AC71-43A05F83243D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"da459d88eafde97f71cab4987133bf98fa868fa9","datavalue":{"value":"location problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q1099951$ADE6E5BD-0491-4186-A096-410BC8C8FFDA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"69bf35491004eec994c27ed7f8f812e978cc9810","datavalue":{"value":"1-line center","type":"string"},"datatype":"string"},"type":"statement","id":"Q1099951$A4C7986F-D564-46C1-B67F-2BC2CF1C66E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f1f1814ebfb0c5873f215208cab188392d4def9a","datavalue":{"value":"lower bound","type":"string"},"datatype":"string"},"type":"statement","id":"Q1099951$AA481954-BCE7-43C7-90FA-FDCDFB99E587","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":"Q1099951$D9C9F23A-C24F-4507-998E-227874F27A15","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"340ea97c0f2f383d364057042ebc9f9438fcc85a","datavalue":{"value":{"entity-type":"item","numeric-id":4091421,"id":"Q4091421"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099951$6CD0008C-2EDF-4EEF-916A-49013A56D1FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a95be383f4814efc07c25732619c12742108f623","datavalue":{"value":{"entity-type":"item","numeric-id":1259164,"id":"Q1259164"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099951$E198D454-34FB-45D0-9959-344C460FA6D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e29b8e47936578f5cad24b50941e85f6a32ad9da","datavalue":{"value":{"entity-type":"item","numeric-id":3738618,"id":"Q3738618"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099951$8AA7FF3A-E0F6-4673-B605-2BE4B01B405F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bfdc76fb3562ef6f4c9173dc95ee70d4835105e7","datavalue":{"value":{"entity-type":"item","numeric-id":4157950,"id":"Q4157950"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099951$709427F9-7289-4C9E-BE86-FB919E306CC6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4b93cbcfe92914798c52148f95cc353b5e256c5a","datavalue":{"value":{"entity-type":"item","numeric-id":2552382,"id":"Q2552382"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099951$9A905557-C4C9-40ED-98F9-33EAD7D35B57","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"813773fa16a57d5ba1f1f634d7f3bafad0c0476d","datavalue":{"value":{"entity-type":"item","numeric-id":3967063,"id":"Q3967063"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099951$3D97AC2E-D0AF-4655-AAA0-4010C549A0E7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a7d8dd1f3c30592e5f77dea55253a0424c56b674","datavalue":{"value":{"entity-type":"item","numeric-id":3768402,"id":"Q3768402"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099951$0D8F8990-5BBD-4BA0-9D59-D2DEFAECAA7B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3a9e941b224ae72629b3e2cd083153eeebdfa379","datavalue":{"value":{"entity-type":"item","numeric-id":3670553,"id":"Q3670553"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099951$C34C3676-28E3-47FC-BADF-90E72C33559B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"26736971b71f38c87ce58e186943954df95eb066","datavalue":{"value":{"entity-type":"item","numeric-id":1837617,"id":"Q1837617"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099951$8C84F9A8-8C6E-499D-BC7A-AD1827673571","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"67e212ad65820abdc25b43ead75d9f4c07504c2a","datavalue":{"value":{"entity-type":"item","numeric-id":1171985,"id":"Q1171985"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099951$54454C33-0B97-40E8-8C0D-263D954C8777","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"be31cf64db6518ed5535ba9b1440297774588a8e","datavalue":{"value":{"entity-type":"item","numeric-id":3854625,"id":"Q3854625"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099951$CEDE211A-19A2-4AFA-B625-4325A993A4D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f62acb5eac89db2e3c6032dabab2d88e9279dd27","datavalue":{"value":{"entity-type":"item","numeric-id":4110607,"id":"Q4110607"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099951$9836131F-D7E2-4836-9FAC-BEC6FB37B352","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"43d43f926304af656560186bb34ae2943c1894d1","datavalue":{"value":{"entity-type":"item","numeric-id":5659062,"id":"Q5659062"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099951$6040A553-A3B8-4F57-9108-49636BC6371D","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"0f786db0cbb8a560c3447af0b4803581c31410d9","datavalue":{"value":"https://doi.org/10.1007/bf01840442","type":"string"},"datatype":"url"},"type":"statement","id":"Q1099951$F7990F71-1958-4F86-B1CD-D5DAC7ED1A67","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"021ed53890cfda94e24f1fa07211fd6b541854f6","datavalue":{"value":"W1998932824","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1099951$FCFD387D-BFF0-4D90-9725-FDC506A2F096","rank":"normal"}],"P1643":[{"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":"c4bfdd565fb8fa84bfac3af1425fede3ac5fff61","datavalue":{"value":{"amount":"+0.98185664","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1099951$C6DCD873-4926-4012-97C8-359A8C04ABD6","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":"52438bebacb4a1dae31978af18c3c200759e6be7","datavalue":{"value":{"amount":"+0.97372425","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1099951$21C9014C-9893-46E9-8AEF-0036917A5095","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b05eaff7131db9be73bc09ef67a554fd9b9b2afd","datavalue":{"value":{"entity-type":"item","numeric-id":4024323,"id":"Q4024323"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5b5b1826c4c3fe91a91daa5ca584faa67221ba6e","datavalue":{"value":{"amount":"+0.9367887","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1099951$6BD55551-A359-4ECA-B492-9E7F5CFD82AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7e130b68b353aafbe7fe0449ccec2cc051b52886","datavalue":{"value":{"entity-type":"item","numeric-id":1122367,"id":"Q1122367"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3837b8f06339540b29c006d53b8d8de6a55375b4","datavalue":{"value":{"amount":"+0.89761204","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1099951$99551F45-7778-4DC0-A919-0238C582A534","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7ec50d0f4d065416e772c4ef49a5eb08e7b184f0","datavalue":{"value":{"entity-type":"item","numeric-id":683940,"id":"Q683940"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4f151446ee51c8aa7b6fda17731ac8d412c9396b","datavalue":{"value":{"amount":"+0.8947848","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1099951$CF5CCAB2-DACD-4522-862B-D2E8EC1D2D8A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4d285933c99e5dddbf1cf70bb39755cc5d0ae116","datavalue":{"value":{"entity-type":"item","numeric-id":5050005,"id":"Q5050005"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"832f1f03642df796a54dc45dcc35bbbad3b160e0","datavalue":{"value":{"amount":"+0.89328045","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1099951$0CD9C2ED-CF0F-4FCC-9D6F-44462D3FEE51","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5dffa030692c5b98bcd16bbae6f64113de89d919","datavalue":{"value":{"entity-type":"item","numeric-id":6089667,"id":"Q6089667"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"832f1f03642df796a54dc45dcc35bbbad3b160e0","datavalue":{"value":{"amount":"+0.89328045","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1099951$65B0450A-4C04-4A8E-A5DC-79E2E8EA39D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a0847d91409288e7df2e47da045bd392af3c7b4b","datavalue":{"value":{"entity-type":"item","numeric-id":5856668,"id":"Q5856668"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"066a83650a3b5f59b0661dfb3b4e72a537e48f4b","datavalue":{"value":{"amount":"+0.8895705","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1099951$D6F2F085-A3F5-44D1-8674-A9A86BC21723","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"574d5c72d42f83511d65e4c91b04f138ad362841","datavalue":{"value":{"entity-type":"item","numeric-id":1289016,"id":"Q1289016"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"29f861dcd78cc176b64e273c08d3a4e8b417b7c9","datavalue":{"value":{"amount":"+0.8876665","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1099951$4335F521-720C-4ABE-B558-288449D6CA84","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Geometric complexity of some location problems","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Geometric_complexity_of_some_location_problems"}}}}}