{"entities":{"Q1087340":{"pageid":1098092,"ns":120,"title":"Item:Q1087340","lastrevid":42866028,"modified":"2025-07-15T13:03:46Z","type":"item","id":"Q1087340","labels":{"en":{"language":"en","value":"Visibility of disjoint polygons"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3988750"}},"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":"Q1087340$6FE6FE2A-22D9-4970-AD8B-C8455676C89A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e2eab8b3dbbafb41ee2ab39927679b505b3a4610","datavalue":{"value":{"text":"Visibility of disjoint polygons","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1087340$40DE8B00-A7A8-4EBD-938B-44934CF12966","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"4c3ace6d21a05eeb538ec5294e581bf17a7ba1a3","datavalue":{"value":"0611.68062","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1087340$2D03E49C-5B63-4752-AFC1-F4CBC650F4BF","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"2acddcbffed2903383c61abbf39c838d1357c80d","datavalue":{"value":"10.1007/BF01840436","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1087340$3E2855AB-C3CB-4ADD-B86F-DCFEFCFECB2A","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"0608c28dd6e3edb1ad2e60313b9ab4c48668656b","datavalue":{"value":{"entity-type":"item","numeric-id":406636,"id":"Q406636"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1087340$EFDA4E51-D68A-41C0-AE4F-E1E0BD3871C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ca0f809e75b605da89222285942806748678a6ab","datavalue":{"value":{"entity-type":"item","numeric-id":390166,"id":"Q390166"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1087340$8E345BEC-6762-40F0-82DF-C2C471BAE901","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"eda441f92ca7e4b15fcf89b60e9369446b66496e","datavalue":{"value":{"entity-type":"item","numeric-id":583231,"id":"Q583231"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1087340$66819E9D-D649-4D4A-B16E-676FD7DCF03C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"27055c7a0af767b1f36b14e7674bc0aa2224fdc0","datavalue":{"value":{"entity-type":"item","numeric-id":534491,"id":"Q534491"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1087340$61F0E1C8-6336-4655-BCB2-B293CFA13171","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"94eab6fdb0a0437dc92c234ddacb5446e0f8992e","datavalue":{"value":{"entity-type":"item","numeric-id":1384195,"id":"Q1384195"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1087340$ED199E78-26AF-4CED-920A-6D6AABED0BCE","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":"Q1087340$4967FA1D-C4D2-4CD3-A952-F6FCD5D00F44","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":"Q1087340$460D4AEF-0A98-47D5-A5C8-AC7BA960A3F6","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"bfbfc4bf507fb6b15af7732fe293c7fb8aa9c15d","datavalue":{"value":"Consider a collection of disjoint polygons in the plane containing a total of n edges. We show how to build, in \\(O(n^ 2)\\) time and space, a data structure from which in O(n) time we can compute the visibility polygon of a given point with respect to the polygon collection. As an application of this structure, the visibility graph of the given polygons can be constructed in \\(O(n^ 2)\\) time and space. This implies that the shortest path that connects two points in the plane and avoids the polygons in our collection can be computed in \\(O(n^ 2)\\) time, improving earlier \\(O(n^ 2 \\log n)\\) results.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1087340$1D766D8B-7A80-4AC2-A8AA-DC3CD6FE2F9D","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"61f5e4db0e91212ef2106e3db512d71730a68751","datavalue":{"value":"68U99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1087340$17D6928B-DE99-4EAB-9088-9C2E6D2ADDD9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1087340$B27494F1-ED9D-40E2-8CA7-F3938CE53BD1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5ae9e2988e76d371f7e87b79bcd004ea2b80f64","datavalue":{"value":"51M20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1087340$C25E71B6-AF91-4F5E-A9ED-3B8DAF23D014","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"809b18b2b61d0942af4c360e6018e383e21540f1","datavalue":{"value":"3988750","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1087340$575E7252-6144-4607-B25B-3B6E31515110","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"551d108313cfab3a77b395a647aede7021169ebd","datavalue":{"value":"computational geometry","type":"string"},"datatype":"string"},"type":"statement","id":"Q1087340$15DAC84C-EEB6-4368-9191-E0F48B5D577D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"423372722ffce52d92ff0a29cab429fa342d34e2","datavalue":{"value":"computer graphics","type":"string"},"datatype":"string"},"type":"statement","id":"Q1087340$7DC2AD69-2091-4C20-9329-BCC33DB99DEF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"baa401a90f7be40837e492046fd0146ae8e354d2","datavalue":{"value":"robotics","type":"string"},"datatype":"string"},"type":"statement","id":"Q1087340$3493EFE4-556C-44BA-9202-ADAEA5B9E5D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a9451439191c446dc6c6f6bef72beef2d3f00368","datavalue":{"value":"hidden-line elimination","type":"string"},"datatype":"string"},"type":"statement","id":"Q1087340$18EB4A0B-2D59-49C8-A891-C5DB45EC6E7F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c25bc710e4a99b4ad5c06b7d722ebbdb9259ca1e","datavalue":{"value":"data structure","type":"string"},"datatype":"string"},"type":"statement","id":"Q1087340$F0478007-E2D0-43AF-ABB1-21BE0C25F29D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d98e7d827365e57da8d5f90594cd92957f90994a","datavalue":{"value":"visibility polygon","type":"string"},"datatype":"string"},"type":"statement","id":"Q1087340$CD8957D9-5E54-45F2-9E59-ED4F63C5D54A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"789386d2db874eb7c464a6c6adbdc90ff4738811","datavalue":{"value":"visibility graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1087340$C0351BD4-D306-41B3-8F4C-7A5F02FD78AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f85e9f2721221f48af2e899508349c71e3faa29f","datavalue":{"value":"shortest path","type":"string"},"datatype":"string"},"type":"statement","id":"Q1087340$AA1A3B39-9097-4FD4-89EE-DB8BD7BE3D07","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":"Q1087340$47F9BCC2-587E-4268-9F40-2DFCBC581EF9","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"eb71e38ab0216024ec0690b1685e409899a3aead","datavalue":{"value":{"entity-type":"item","numeric-id":1082821,"id":"Q1082821"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1087340$1ACEF3CB-E8A2-401C-96CE-945C7BB5E31F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d0bb2a78ba34e8728e91d77da2bf6df4e36bb56c","datavalue":{"value":{"entity-type":"item","numeric-id":3740283,"id":"Q3740283"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1087340$44767340-9248-42A0-AD07-B28583E35FD9","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":"Q1087340$EDDFE3C4-32E9-439F-B120-F7F253CB5C5B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"17b46f23e1d95210ec444c78dd7a8edd18f2e48d","datavalue":{"value":{"entity-type":"item","numeric-id":1062461,"id":"Q1062461"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1087340$C26152F7-4294-458F-82B5-674DCD2E4A17","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4ae0713540eb691df7bd8820bc004fcb597f484c","datavalue":{"value":{"entity-type":"item","numeric-id":1249042,"id":"Q1249042"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1087340$A18DAC31-8EAD-465E-B4B4-B7A01D979201","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":"Q1087340$D93B3C6D-C99A-4C83-9F66-CEEE10682EF3","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":"Q1087340$20FF0D6A-9ABB-4770-97A4-A723D39E0FE0","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":"Q1087340$7AC034B5-678E-4E61-A334-787CE2B50ED3","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"268b4d19442d4cf81a9575ebed6f5874a96d951a","datavalue":{"value":{"entity-type":"item","numeric-id":3315016,"id":"Q3315016"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e278e30921e4ec3011c6bb6eb5cd04ed20f48a0c","datavalue":{"value":{"amount":"+0.9012465","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":"Q1087340$FF4F07EB-CBDE-4AB9-A52C-70F46165D4A7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f87e2f72be2cdfeee698041d46ff5679d2000a29","datavalue":{"value":{"entity-type":"item","numeric-id":3808786,"id":"Q3808786"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"457d1a22043a3c86bf7a481837bda30e35881074","datavalue":{"value":{"amount":"+0.8999485","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":"Q1087340$F95B704E-F3B8-4351-9BB9-C844E1F40956","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"55766e4f8f2f5459e7c2f4156c933224dd50a7f2","datavalue":{"value":{"entity-type":"item","numeric-id":3139724,"id":"Q3139724"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d629fc32158d9be7cb4326f9c0215716f059f30c","datavalue":{"value":{"amount":"+0.8894924","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":"Q1087340$ADB09D73-EA36-4725-B692-AC12FB62C649","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":"22d1cfca1c11787a18829d20481b49cfa41ba7a6","datavalue":{"value":{"amount":"+0.8880287","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":"Q1087340$C34E3760-DFAB-4331-9E80-6A9B482E939C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d5d82c9060d7fb56a1245a0d9abe633e515acc10","datavalue":{"value":{"entity-type":"item","numeric-id":833709,"id":"Q833709"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ab3efd21b4888818c865cefc848c6f7ec6ade4e8","datavalue":{"value":{"amount":"+0.8838978","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":"Q1087340$4C4B2584-FF5F-4174-B81A-94FF26BE7CEE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"78dfacc94f10fdc8b3125c208bd25c31d9888ff4","datavalue":{"value":{"entity-type":"item","numeric-id":375935,"id":"Q375935"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"87a77570b046e0f9722e3475af72bb3abb1c2df9","datavalue":{"value":{"amount":"+0.88365793","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":"Q1087340$182AF26F-FEA6-4600-AEBD-BB0B452FFA58","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":"3fccfeae09fdaf74b91aab8930f71b0a9b4c6004","datavalue":{"value":{"amount":"+0.883392","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":"Q1087340$8109E677-72F2-4A80-832B-42371B8C84AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"334c4b9886c8f442329c6d7fa7dde131c84dfda9","datavalue":{"value":{"entity-type":"item","numeric-id":1611059,"id":"Q1611059"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d9fbcc4f66483d12d3809afb45e30d2f8178b1f2","datavalue":{"value":{"amount":"+0.8831471","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":"Q1087340$6123920E-A0FA-4CCD-9CE8-6701E9682018","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3c32d8651d1f4a099658061e78594f3a91a86959","datavalue":{"value":{"entity-type":"item","numeric-id":5361651,"id":"Q5361651"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8f9766e9d1a13ccbe92906cedd26db2ba7235c80","datavalue":{"value":{"amount":"+0.8825358","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":"Q1087340$6FB135F2-78AD-4EE2-83FD-1AA4F1F8C95A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1087340","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1087340"}}}}}