{"entities":{"Q2367125":{"pageid":2377868,"ns":120,"title":"Item:Q2367125","lastrevid":46347903,"modified":"2025-12-24T15:02:44Z","type":"item","id":"Q2367125","labels":{"en":{"language":"en","value":"Minimal link visibility paths inside a simple polygon"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 232806"}},"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":"Q2367125$46495AF9-4FE3-4AD6-B518-5BB30CEF589A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"063759ae4d01b919f089c7ea6774acdeee7fc2b8","datavalue":{"value":{"text":"Minimal link visibility paths inside a simple polygon","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2367125$34224EF9-847A-4929-BACA-F519BDBE8A85","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"9ab91e6f27cf5f399249feba56c775eb264002b6","datavalue":{"value":"0789.68138","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2367125$3F649814-8B14-40F9-97A5-92B070280B6A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"11b2e1114ac8e4154035ca0415a913d9c571451f","datavalue":{"value":"10.1016/0925-7721(93)90027-4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2367125$026C2F09-7942-4769-B07E-3EB6A66C8A12","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"cc45e6b9322bed7360e4aac2a42f8c73614b44f3","datavalue":{"value":{"entity-type":"item","numeric-id":1787138,"id":"Q1787138"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2367125$8B84F5AD-D444-4C13-9401-75599AB1B09F","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":"Q2367125$B91AED6A-0848-4174-938B-FDFFEED94D2E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"cac67b5af44da91dcbd20e8bc235f3b14eeda006","datavalue":{"value":{"time":"+1993-08-23T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2367125$075B4D04-6EF4-46A6-9BE5-93B16669EE99","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e974d828e76eeee3267f1ba5782fa1ae565a7728","datavalue":{"value":"The paper shows that the following problem is \\(NP\\)-hard: Given a simple polygon \\(P\\) in the plane find a polygonal path \\(\\pi\\) with a minimum number of edges so that any point inside \\(P\\) is visible from some point on \\(\\pi\\) (``minimal link visibility path''). In addition it is shown that it is \\(NP\\)-hard to find a minimum link tour inside a given polygon \\(P\\) visiting a given set \\(S\\) of points on the boundary of \\(P\\). The reduction is from the settheoretic Exact-three-cover (\\(X3C\\)) problem. The paper also presents a polynomial time algorithm for finding a visibility path whose link-length is at most three times as long as the optimal one.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2367125$55C136BF-5C1F-4183-A527-C39FCD17283A","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"0aa8d3ac5bbff6b41e0a3e53ebafb780beece760","datavalue":{"value":{"entity-type":"item","numeric-id":441885,"id":"Q441885"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2367125$1F026B5E-A63E-4DFB-9361-20E75150984C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"159426a5937e62cfbbcc198dd4848ab52d6e715e","datavalue":{"value":"68U05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2367125$B6B64FE3-8B08-4717-AC1A-F158AB30BEAC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2367125$39109084-8F81-4197-B6D6-4F4844E79EDC","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"2b9e4057343509aafc1c09112319c4537f289c07","datavalue":{"value":"232806","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2367125$49BE2795-8555-4BC4-8137-F95C724A4EA3","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"551d108313cfab3a77b395a647aede7021169ebd","datavalue":{"value":"computational geometry","type":"string"},"datatype":"string"},"type":"statement","id":"Q2367125$75EC92F0-EC32-4A89-B73F-E0DD063B9FFA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1a5154985a09ded3c6af9f8ca1100f6f4d1d46cd","datavalue":{"value":"\\(NP\\)-hard","type":"string"},"datatype":"string"},"type":"statement","id":"Q2367125$C7177F15-B478-43B0-8F23-DC57CAD89B73","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7bfd605e8d1eec2e403cfe1b9f8fb6385b43b4a0","datavalue":{"value":"visibility","type":"string"},"datatype":"string"},"type":"statement","id":"Q2367125$6341E7A6-1869-4367-B056-90B7318359B7","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":"Q2367125$24DCF391-BEBD-4A46-9BD1-D6D50508B073","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"7243773d909d37d3dbac0cacdf1bc75dcc7988eb","datavalue":{"value":"https://doi.org/10.1016/0925-7721(93)90027-4","type":"string"},"datatype":"url"},"type":"statement","id":"Q2367125$37BB62A8-855C-4D19-AA22-F0AA55820E57","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"140cc9ca19611affb16c8666b3f38636bdd6d311","datavalue":{"value":"W1989185470","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2367125$C0D470CA-8AFA-4A82-95EA-369E292BA7C2","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"32075ec04907693f54183313f1daa42a26b4f2b7","datavalue":{"value":{"entity-type":"item","numeric-id":1107312,"id":"Q1107312"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2367125$BE935581-96C2-49A3-BA83-159C2551070C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"42ed11ddcc48601d16ea2a43604c46e30a27b7a7","datavalue":{"value":{"entity-type":"item","numeric-id":751818,"id":"Q751818"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2367125$B798BB54-86BE-45E9-ABCC-BC2B11B3AB4F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fc2781f3435f018695eb5229346a1bee1b070afd","datavalue":{"value":{"entity-type":"item","numeric-id":1193703,"id":"Q1193703"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2367125$E55D7096-DCEF-4B9D-98A2-8857523E27A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6ff1af2b4b0acfb50ca62ddd7ca7021cc3edcb47","datavalue":{"value":{"entity-type":"item","numeric-id":3910036,"id":"Q3910036"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2367125$CC45A630-B933-446B-A60B-D74DD007A551","rank":"normal"},{"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":"Q2367125$C97AB4E7-F2FA-4A40-8352-225C69D0B7CD","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":"Q2367125$F482ABA7-0B59-4F1A-8E0F-DA479F47B539","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f3e4ab0d9c6453b2a26963b982b5c427c53ec041","datavalue":{"value":{"entity-type":"item","numeric-id":4188754,"id":"Q4188754"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2367125$DA8B8D32-DC1D-4C69-A8A6-E2C217C5501A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"085e1218a66243e307498d7e8b0c1d323937d638","datavalue":{"value":{"entity-type":"item","numeric-id":3337244,"id":"Q3337244"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2367125$C3CB7F00-929C-4B2E-BC4E-79444CDD6428","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4d9f4c44af503a85955b4792a2514c09bdc5c3e0","datavalue":{"value":{"entity-type":"item","numeric-id":1104086,"id":"Q1104086"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2367125$8A655411-5594-4394-A8DD-3A9DBDA407AB","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":"Q2367125$F30E5E99-2008-4F90-B93D-77B2AE5F71E1","rank":"normal"},{"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":"Q2367125$3376D627-7149-44B8-BBA4-F39FB70B4FB6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"45ce96ee513514e815725e851b3daeaea5391a2f","datavalue":{"value":{"entity-type":"item","numeric-id":3026389,"id":"Q3026389"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2367125$ACCCDB3F-217D-452D-8149-D611B1349AD0","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a371a414037bf45ae2b4bcf722055904c48dbf45","datavalue":{"value":{"entity-type":"item","numeric-id":672401,"id":"Q672401"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dde90b4bb7c8f4ec533b9ce41ab7df40ed90667d","datavalue":{"value":{"amount":"+0.8829190731048584","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":"Q2367125$9B3EA615-2264-4DF3-8ED7-AF680FCDDA2B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2a877a82d1956a6846dba89ac7ef4810274ea891","datavalue":{"value":{"entity-type":"item","numeric-id":1007602,"id":"Q1007602"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6e89f0d13730c92d6f8c7c350d408b1c7ba372a9","datavalue":{"value":{"amount":"+0.8266276121139526","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":"Q2367125$AA7DCC41-E4A0-4ADB-806D-728E6128064A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"63af3600ed1dd6fd4f5131545f6b2ae2ea1c8cd3","datavalue":{"value":{"entity-type":"item","numeric-id":811138,"id":"Q811138"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2ac8f3e24f8bd60cb2165e7d2684234ca7ba9a5a","datavalue":{"value":{"amount":"+0.8103594183921814","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":"Q2367125$107B3C93-DA3E-4A56-A7C4-EBBF8EA3DA4F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c8ea9fcde6745790281bcc99ad96d95384a52c5f","datavalue":{"value":{"entity-type":"item","numeric-id":3132885,"id":"Q3132885"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e5ad16862fe2e3998f1fb72b4ab8c02c83fd9330","datavalue":{"value":{"amount":"+0.8082413077354431","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":"Q2367125$A66F4FD1-0572-4AB5-B8E6-E82C47F6C31A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2367125","badges":[]}}}}}