{"entities":{"Q513290":{"pageid":515057,"ns":120,"title":"Item:Q513290","lastrevid":55915117,"modified":"2026-02-21T02:52:09Z","type":"item","id":"Q513290","labels":{"en":{"language":"en","value":"Computing the visibility polygon of an island in a polygonal domain"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6691976"}},"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":"Q513290$0AAE32F8-B63F-40FF-B831-87A002A18073","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c82710f2b43f0d9a58b88693fc5c6db505b68e17","datavalue":{"value":{"text":"Computing the visibility polygon of an island in a polygonal domain","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q513290$BCE917E2-4418-4FE7-BA40-53B9ED1C2FC3","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"b2e6fe9d1a5d89ba193ef7cc9bac675e715f410d","datavalue":{"value":"1364.68343","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q513290$4D1353E0-383A-483C-91B9-3ADC7296B2B1","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"45f6a7d29d05afbeef43db5dfb68629047eebcd1","datavalue":{"value":{"entity-type":"item","numeric-id":185435,"id":"Q185435"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q513290$9620ED35-1824-46B8-AB4E-B2A9DE1EE088","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ee77e9e802f8ee02fdf572c830e5e79fb5cbb2f7","datavalue":{"value":{"entity-type":"item","numeric-id":297368,"id":"Q297368"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q513290$25F0DDBD-E3FA-4DAA-BC04-E6F9BDA9F346","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":"Q513290$3660EA21-01FA-4C6E-8254-4A40426EFB2D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"29f5b11f428488ca09b98e4f34562f43d3b169f9","datavalue":{"value":{"time":"+2017-03-06T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q513290$18551794-4169-4A10-9BE3-399612998B3D","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"557b13aa2bbe974a6ca72ae2d633ab4fb7b0d723","datavalue":{"value":"This paper focuses on the problem of computing the (weak) visibility polygon from a polygonal obstacle \\(P^*\\) (an island) in a given set \\(P\\) comprising \\(n\\) vertices and \\(h\\) pairwise disjoint obstacles. The authors show that the complexity of previously proposed algorithms, \\(O(n^4)\\), can be improved as a function of \\(h\\) and present an algorithm of complexity \\(O(n^2h^2)\\) when \\(h=o(n).\\) Moreover, when all obstacles are convex, the complexity is reduced to \\(O(n+h^4)\\). The paper commences with an overview of the problem and the introduction of preliminary concepts such as the corridor structure, bays and canals. The SO algorithm is also briefly presented. Next, the authors describe their novel approach, focusing on three types of edges and the illumination gates and their role in computing \\(\\mathrm{Vis}(P^*)\\). The paper concludes with the description of the new algorithm applied to the convex version of the problem, i.e., all obstacles in \\(P\\) are convex polygons, which focuses on generating pseudo-triangles and using them to compute the union \\(\\mathrm{Vis}(P^*)\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q513290$EC78864F-7F0F-408E-9E4C-1AED464958DE","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"035c7fc61d6c9f8d0118c86401c2039cb42ea2e6","datavalue":{"value":{"entity-type":"item","numeric-id":590640,"id":"Q590640"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q513290$90389F81-46BA-4EA8-8D5B-BFB20D8A58D9","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"159426a5937e62cfbbcc198dd4848ab52d6e715e","datavalue":{"value":"68U05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q513290$D4A776CF-371A-4821-A058-4308DC43B524","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q513290$17F45540-1F26-4D99-81E4-F5D9704A09B0","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"bc4a899e1cdce14643ab2377f2bfdd6e4d2fffdd","datavalue":{"value":"6691976","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q513290$D26D2450-AD74-4EB2-A84C-8085025140C6","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4879833d2a6cfb729c1041914e5874ec92e04c00","datavalue":{"value":"visibility polygons","type":"string"},"datatype":"string"},"type":"statement","id":"Q513290$40184F39-D4D9-47B2-9C38-2E3F00816140","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b69dc0098c6a2e161109e5cbe189345443cbc757","datavalue":{"value":"polygonal domains","type":"string"},"datatype":"string"},"type":"statement","id":"Q513290$B3B636F4-2F1C-4DF3-9345-E00F0472ECF0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"70dec4d3819629e30769f04575369e72be128427","datavalue":{"value":"polygon with holes","type":"string"},"datatype":"string"},"type":"statement","id":"Q513290$83F11C92-663D-4C20-8178-56E70C6385C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d607627523840bd0bf4407097f29a3a99ef4a0a8","datavalue":{"value":"algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q513290$9AEB787E-C9B0-4F67-860F-D7BEC81BECBC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"551d108313cfab3a77b395a647aede7021169ebd","datavalue":{"value":"computational geometry","type":"string"},"datatype":"string"},"type":"statement","id":"Q513290$35BE6208-23BA-4D91-B7AC-DFB6D7BBB1A8","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":"Q513290$743C8E5A-D489-43C0-870D-FDD73D3FB904","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"9549b9c5dde07b0c01d880fadaed0369c728f6b8","datavalue":{"value":"https://doi.org/10.1007/s00453-015-0058-y","type":"string"},"datatype":"url"},"type":"statement","id":"Q513290$C9C7FD83-B040-4955-B513-20C5851F3782","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"6a264562ff4270dc5c3bcc5cc540e71701e8d918","datavalue":{"value":"W2165366584","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q513290$AF125712-0662-4971-B5CE-DFC43A15D000","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"aa1ba3f58e2231825bfce74b74cabb3c6d2ddd9e","datavalue":{"value":{"entity-type":"item","numeric-id":1087340,"id":"Q1087340"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q513290$C0FFDD09-C45A-4263-B4C0-E33092422665","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ef64418f45614f31a738adad1ef25f7272a1fa63","datavalue":{"value":{"entity-type":"item","numeric-id":4302845,"id":"Q4302845"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q513290$2516FBD6-95F4-4B43-A4A6-CAED7A64BF3E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"30491d0bbe2953f70f7a05be7ecea1e361c7bfa4","datavalue":{"value":{"entity-type":"item","numeric-id":1974462,"id":"Q1974462"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q513290$E0F06C4A-AE01-47DC-8747-553556B56190","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1527977d1e97f551ee80e9595c567d4fb5b3ce20","datavalue":{"value":{"entity-type":"item","numeric-id":1176324,"id":"Q1176324"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q513290$1B45493B-A9B4-449F-84F8-10D1F989DE37","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4124ad3652fc359ba98d227348be70dfb6e4acf5","datavalue":{"value":{"entity-type":"item","numeric-id":910213,"id":"Q910213"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q513290$DE171AA3-9C4C-4AA3-8A9F-C99BD8D2A836","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e5e4de16c9f88c6c78137d76736d10b808b7a3b5","datavalue":{"value":{"entity-type":"item","numeric-id":3092254,"id":"Q3092254"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q513290$11151273-70C4-4B3A-BB17-68FD10349780","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5ce61cd46e6386a4ea9ada0e9d0bdd8491af217f","datavalue":{"value":{"entity-type":"item","numeric-id":2261573,"id":"Q2261573"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q513290$A3F880B8-7F47-40A6-A8A4-09FDC7D1DA34","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":"Q513290$E2ECAF7C-EA71-4250-9BB4-82BCEC632ABE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8e2d63beb185dfd3ad09ac057e0d8bb1a8bd81dd","datavalue":{"value":{"entity-type":"item","numeric-id":5750463,"id":"Q5750463"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q513290$6B9ACED5-785E-471C-9D43-9DA1308214EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1b32de81f138bfd0051adfbd8bd15bcb529446c0","datavalue":{"value":{"entity-type":"item","numeric-id":3982713,"id":"Q3982713"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q513290$6F2CF608-CB3C-4168-AD7E-0050824D945D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d2c6b273bbbfb23a71b64948d50760d60883087e","datavalue":{"value":{"entity-type":"item","numeric-id":1101226,"id":"Q1101226"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q513290$627C9301-0AD5-47C0-8837-32C6C589F4E8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"020a9ade70af16eeda6ed3b808699b87bfd4fd88","datavalue":{"value":{"entity-type":"item","numeric-id":4326861,"id":"Q4326861"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q513290$7914600D-3650-4122-8C96-DE947C2E8489","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"aedcb665a5e42e34aac05399421a39f6a3f0357e","datavalue":{"value":{"entity-type":"item","numeric-id":833714,"id":"Q833714"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q513290$3FB5F9D5-C59B-4BF9-BFE1-25B5E04B5662","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"faa054148645c13cc771f9542df10139936fa7e2","datavalue":{"value":{"entity-type":"item","numeric-id":4009735,"id":"Q4009735"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q513290$82121149-2781-4683-A649-53227343E09A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7a54274ce572d3c34835d187957120beffafc780","datavalue":{"value":{"entity-type":"item","numeric-id":1102120,"id":"Q1102120"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q513290$533C6EB3-A2B0-47E7-8A99-B74242B7626F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"902aae9f2a23ad42c0b9aac5d048bc06f389d663","datavalue":{"value":{"entity-type":"item","numeric-id":1380799,"id":"Q1380799"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q513290$78B9CC2C-48AC-4B81-88A3-1D2493F60C80","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"74caa8dd26dc163a670e2aae9e70cc7322d01346","datavalue":{"value":{"entity-type":"item","numeric-id":3315016,"id":"Q3315016"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q513290$CC7FE784-6DDC-4744-A0EF-48761A2B128A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d191d7e957673b201cc5d04ff6afa5bc71ebf986","datavalue":{"value":{"entity-type":"item","numeric-id":3028356,"id":"Q3028356"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q513290$E92D367B-7457-4130-9E24-FA372C516D6C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5b42951d9312bfb6ce2da7dbf87a882a8ebee9b6","datavalue":{"value":{"entity-type":"item","numeric-id":1085615,"id":"Q1085615"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q513290$DC6AEBB7-C412-4F8B-AB39-4C03638D028F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5ffec4d94b7b012095f39126ed96f3bf822347da","datavalue":{"value":{"entity-type":"item","numeric-id":1062764,"id":"Q1062764"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q513290$DC9098E6-02DE-4E82-8995-D24792723C0A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"6ee5bcd5b44dc49e32c0f7a639213721e9ef3cb7","datavalue":{"value":"10.1007/S00453-015-0058-Y","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q513290$B9B122F9-F3AA-412E-A32E-9A9514BF9C95","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"deee9a36de7c3aad3b851dd9c8be7fa2e52c5654","datavalue":{"value":{"entity-type":"item","numeric-id":2843250,"id":"Q2843250"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cad6f1ce96cae7c5c33b8e23dbbf1e686562cad4","datavalue":{"value":{"amount":"+0.846623420715332","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":"Q513290$87B0E093-A273-45EB-AF28-DB4F7E4D4C10","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"010cec3d3a62020297aa1c6718edfb9854e406b1","datavalue":{"value":{"entity-type":"item","numeric-id":3982713,"id":"Q3982713"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"81f1f658b380312d1207442848099c13d88b3d8f","datavalue":{"value":{"amount":"+0.8130371570587158","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":"Q513290$750FF393-3E1C-4EBB-96EF-F7E7A2000A34","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b2c46a224d0197f92640855374ad13816bc93829","datavalue":{"value":{"entity-type":"item","numeric-id":2261573,"id":"Q2261573"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9542300f5827322d28bf1e3bc5aecc6b8c435eac","datavalue":{"value":{"amount":"+0.7764911651611328","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":"Q513290$F278FFC1-ADA2-45EA-A925-CCEF7F43F66D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e6562252c5947f9daebda938cce3dc677b05fc37","datavalue":{"value":{"entity-type":"item","numeric-id":2842161,"id":"Q2842161"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f9da777a75660733a72b5920ad16b3257d75e882","datavalue":{"value":{"amount":"+0.7733423709869385","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":"Q513290$A45DCE28-5DDA-4D2D-A549-215653250377","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:513290","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:513290"}}}}}