{"entities":{"Q2144449":{"pageid":2155192,"ns":120,"title":"Item:Q2144449","lastrevid":55915147,"modified":"2026-02-21T02:52:34Z","type":"item","id":"Q2144449","labels":{"en":{"language":"en","value":"Line segment visibility with sidedness constraints"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7541309"}},"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":"Q2144449$2D745FA2-9AF6-4590-A130-76A45C380EB5","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"7aef332990ec2a0bde532634f3584e5c43c145cc","datavalue":{"value":{"text":"Line segment visibility with sidedness constraints","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2144449$8B5535B6-AE42-4CDD-85A6-B46D67CA6149","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"49f459b09b496a020ffe16be9cd6f572aae432e8","datavalue":{"value":"1502.68330","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2144449$A65FCC6A-97CD-4559-9CC1-8F57E22B5DFA","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"5c2baa8233ec907033e96c6dc8b0d907488b4a3d","datavalue":{"value":{"entity-type":"item","numeric-id":531603,"id":"Q531603"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2144449$871F128E-BECD-41CD-BC68-74D1564196BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"8e0c6dbc7f7d497cf06ee7277126e7056ea95e6e","datavalue":{"value":{"entity-type":"item","numeric-id":543786,"id":"Q543786"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2144449$1F8D1D56-2086-4639-A0C1-09FD738F22E3","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":"Q2144449$826A5D6F-D7F6-41D3-966F-C9BAB7C50F25","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"77075991782c40305711c3d33a7ecd0dd8eab84c","datavalue":{"value":{"time":"+2022-06-13T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2144449$8F57F63F-376E-4548-B6DA-031C40965D88","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"6e08ab0c5ce63fadadb4a8ca9b83e95973d5a10d","datavalue":{"value":"Motivated by the problem of efficient monitoring of the cooling and heat production in commercial data centres, the authors study a variant of the classical art gallery problem. In the considered variant, we are interested in guarding not the entire polygon but line segments in the polygon's interior. In the paper, the authors consider only rectangular art galleries because most data centres are rectangular or nearly rectangular. Moreover, the authors introduce a family of problems that they call ``all-but-\\(\\delta\\)'' coverage, where we allow to omit some arbitrarily small length \\(\\delta\\) along each segment.  The authors present a set of combinatorial bounds giving how many guards are needed to cover \\(n\\) segments in the worst case. They divide the bounds into three cases: (1) all segments are vertical, (2) segments are axis-aligned, and (3) segments are arbitrarily aligned. Next, the authors prove that even in the simplest guarding models, the problem of finding a minimal guard set is NP-hard and that the same is true for the all-but-\\(\\delta\\) variants. Lastly, the authors focus on developing heuristics that scale to the size of large commercial data centres. In the proposed heuristic, the candidate guards are placed within successively finer grids, and then integer programming is used to find a stable solution. To show the effectiveness of the proposed approach, the authors describe a series of experiments.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2144449$144CB650-E257-488B-BA04-8BB402E4A12F","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"159426a5937e62cfbbcc198dd4848ab52d6e715e","datavalue":{"value":"68U05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2144449$EC825F72-E08E-4A8D-8DB0-8FF97CAD698E","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ebffddd69fb4ae65c0db79c857f030aba52c4618","datavalue":{"value":"7541309","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2144449$E0863EE0-F54E-42A2-882D-9431EEB5095C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7bfd605e8d1eec2e403cfe1b9f8fb6385b43b4a0","datavalue":{"value":"visibility","type":"string"},"datatype":"string"},"type":"statement","id":"Q2144449$5779C5B2-5DDA-4776-BB6E-30F600F0AD1F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c1a842b4f4882bc8cbc9e7e5ded22ca87149cc32","datavalue":{"value":"art gallery","type":"string"},"datatype":"string"},"type":"statement","id":"Q2144449$E7F6AE0C-A184-429A-BAFC-7EC9F5AC11AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"19780fea10a1e3fc5c0852bbca4b024c7c12d4d1","datavalue":{"value":"line segment","type":"string"},"datatype":"string"},"type":"statement","id":"Q2144449$43C1B32E-6E20-4EC7-BA58-503A7134AE37","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"eca4d3a3d5299eaa6a0adf82c70bad58f6124365","datavalue":{"value":"sidedness","type":"string"},"datatype":"string"},"type":"statement","id":"Q2144449$5BBFBD9C-2D91-4F0B-9A89-774A0B110B02","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"4e8aff2b8e51ed9533d593cc755cbfae6f7c82e5","datavalue":{"value":{"entity-type":"item","numeric-id":305012,"id":"Q305012"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2144449$5A996192-8E9D-4AF2-BC3A-58249907A174","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":"Q2144449$762F37EA-58CA-44F1-BB0D-469338B10B03","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"2854720a16cc5022537674b91e226c7d4d380b97","datavalue":{"value":"https://doi.org/10.1016/j.comgeo.2022.101885","type":"string"},"datatype":"url"},"type":"statement","id":"Q2144449$D248A99E-ADE7-4C46-9318-11B52D097BC4","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"9ed331d2a7ec64d3114b88961012654d920ab1e3","datavalue":{"value":"W4224980313","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2144449$A7F655F1-FEEE-40F5-B1FC-99E2719AB1F5","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"dcf0a28e0871b677d9eb6c3ebfba0bca17e10957","datavalue":{"value":"Q114195514","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2144449$1F60D8E9-2E5E-420C-8D20-71A3D6EC759F","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"a75892efb8c423df4e08c3a2522f9c8641bb850b","datavalue":{"value":{"entity-type":"item","numeric-id":3799261,"id":"Q3799261"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2144449$8FDBA55A-7AE3-44CB-AFFA-E49D81414DBE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"da6a130fac4b3a2c7d09840d6dea725f6bcccd4e","datavalue":{"value":{"entity-type":"item","numeric-id":3723700,"id":"Q3723700"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2144449$117E90A7-EAFB-4748-B117-DCA4C3725CFB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"914ac3f3e6da015fa5adc6009954b28551acde93","datavalue":{"value":{"entity-type":"item","numeric-id":4945523,"id":"Q4945523"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2144449$F14A4CB3-D734-49FA-BFA9-0E5A9C3CD012","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"88d1e8ee5734b574cce64a44a9da505238e65e44","datavalue":{"value":{"entity-type":"item","numeric-id":1434256,"id":"Q1434256"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2144449$1305CAF9-322E-4C3F-8767-32C51459DA6E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c06ee1013d42cb2a1b53edcb4d0b49da4de64ce9","datavalue":{"value":{"entity-type":"item","numeric-id":1394353,"id":"Q1394353"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2144449$C84D523A-8E98-4E5D-A2CF-627E94389C7C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7f71362c4fcfafc492b0e0abaa8317edeb86410e","datavalue":{"value":{"entity-type":"item","numeric-id":1245840,"id":"Q1245840"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2144449$4613231F-1CF3-4080-8BA4-5F8C1A099C59","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"35f0c6c95f79c7cee88240ca4ec01c6c6d56139f","datavalue":{"value":{"entity-type":"item","numeric-id":3603524,"id":"Q3603524"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2144449$C7B55C41-4B46-4DF1-BF23-AC6DB1375858","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6cc4ffa626dfb412989355fdacd00aa6c226fa3d","datavalue":{"value":{"entity-type":"item","numeric-id":4580094,"id":"Q4580094"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2144449$50B0EAD6-8FE4-4D2B-B623-5404D248201F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cfba955c32dc153431f5c99ab1d6a49daa930c11","datavalue":{"value":{"entity-type":"item","numeric-id":5785127,"id":"Q5785127"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2144449$6A7160CA-5E01-4161-AA7B-77C973BE6C00","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"ba19273e06e2313cd1a2986484236d70d84974ea","datavalue":{"value":"10.1016/J.COMGEO.2022.101885","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2144449$320D0794-E0D5-45AD-A8C7-FB951E9B0394","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d4885949607118bf7e8e0d5b3d2684645e928f4a","datavalue":{"value":{"entity-type":"item","numeric-id":1198072,"id":"Q1198072"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"31a30868f968d9b57fa3df267fae7db03130f5bd","datavalue":{"value":{"amount":"+0.8556956","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":"Q2144449$776772EA-9702-4CC6-B519-5889B71BB361","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1a2454ff14b6f116c30024a245d5b3aa5e7688a9","datavalue":{"value":{"entity-type":"item","numeric-id":4033762,"id":"Q4033762"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"48d7e39dd22668e29b98323400f8bf0c1d045d4d","datavalue":{"value":{"amount":"+0.848717","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":"Q2144449$F23DDC49-6FB6-47FD-9E7A-76D3537D10D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d4b43f5f5bf6108bcdec7c27dc2d793f93c69a09","datavalue":{"value":{"entity-type":"item","numeric-id":1087340,"id":"Q1087340"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e56a9eab010c6a0a9ae7910d87230967d34fb6fa","datavalue":{"value":{"amount":"+0.8472809","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":"Q2144449$63FAC9A9-7740-4299-AF5C-DA8EAC401306","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9f5a2c0c210d3b9805ef4cb64bbaac8b1a81908c","datavalue":{"value":{"entity-type":"item","numeric-id":910213,"id":"Q910213"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"75565ef60949cd73ce1257411729ff1e78896fb1","datavalue":{"value":{"amount":"+0.846282","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":"Q2144449$37BB8C4C-BA04-44D4-8D85-91E6A8A220D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d7bea1049a6fb413f4eeacf933e3261568c14901","datavalue":{"value":{"entity-type":"item","numeric-id":3973281,"id":"Q3973281"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2aff98f584cda8a6c1f56c6c853709f3ff67c498","datavalue":{"value":{"amount":"+0.84342545","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":"Q2144449$58C47942-0BD4-49A9-A1A1-945B3FB17DBC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e07cf36c1f2d4ee0a97000dd6f6809efee8a1785","datavalue":{"value":{"entity-type":"item","numeric-id":1096432,"id":"Q1096432"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7c0e8c6fb1f62fee002c005d8bb7fc70ae5df568","datavalue":{"value":{"amount":"+0.8414393","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":"Q2144449$850A610F-6F90-4D78-8D91-EEC74CA3EFF2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2a065106b38fa6ed52eb37c7b62b3abf88c5b5e9","datavalue":{"value":{"entity-type":"item","numeric-id":1375948,"id":"Q1375948"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6734a60815fe29d0b16ba9cd4b0ac2388aff276f","datavalue":{"value":{"amount":"+0.83847356","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":"Q2144449$28E1FDC6-0147-4307-9CC0-6106C8B674DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9c82f96e31f1e4aa3d2d688e84ede6deddc6db6a","datavalue":{"value":{"entity-type":"item","numeric-id":1581056,"id":"Q1581056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c6fc39f7508cca7fb1f55427af3f06dde433e3fc","datavalue":{"value":{"amount":"+0.83791125","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":"Q2144449$E9022A86-26FD-4364-A2B6-D8177B3D203B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2144449","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2144449"}}}}}