{"entities":{"Q390140":{"pageid":391907,"ns":120,"title":"Item:Q390140","lastrevid":51909638,"modified":"2026-01-20T12:48:32Z","type":"item","id":"Q390140","labels":{"en":{"language":"en","value":"Triangulating and guarding realistic polygons"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6249151"}},"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":"Q390140$86A87D53-BCA4-4509-B3D0-7423B7135AE3","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"4b439bceebb6bc3d9da060d2f15436483e307f3e","datavalue":{"value":{"text":"Triangulating and guarding realistic polygons","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q390140$41D37DB5-F232-4AD7-8439-FF984217494F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"de4973c16badc92d656859d523077c4fb3532703","datavalue":{"value":"1314.65028","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q390140$C611A70A-31DE-4F83-9473-FF59C35713C8","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"bef0a5c9c154a2abeb5014d229ef5a5b37626ff8","datavalue":{"value":{"entity-type":"item","numeric-id":390137,"id":"Q390137"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q390140$8B7400FA-7A0F-4AE6-A990-6B6ED921BE74","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"22f6b12f56f2aa9fd0d8aea816f351f53d73fd4f","datavalue":{"value":{"entity-type":"item","numeric-id":223040,"id":"Q223040"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q390140$AC467EA1-65F9-4F98-B4E3-A4A0E09AF68A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"34323737e65ec23e5b5f138b40eff9f6aeba6f57","datavalue":{"value":{"entity-type":"item","numeric-id":390138,"id":"Q390138"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q390140$60A08C86-6545-46A4-B38D-24986352273E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"49b6c5d4c1f37906412743bace47ebd12f9df50e","datavalue":{"value":{"entity-type":"item","numeric-id":390139,"id":"Q390139"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q390140$6A6689A5-EBDC-4F50-B392-C4101D37838A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"79d55a9604167571ae538494962bc1dbdd91abc7","datavalue":{"value":{"entity-type":"item","numeric-id":243581,"id":"Q243581"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q390140$6C695DC6-0C3D-4631-916F-8F2C2BD95966","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"8cfd1671846e1390c3c5805fb8c66f85b8c6f61e","datavalue":{"value":{"entity-type":"item","numeric-id":283882,"id":"Q283882"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q390140$E157F736-E1B2-4763-BC47-191AB97FF180","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":"Q390140$37A229AA-3D67-4A1C-A004-0D996B1B9F5F","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"4faea9ea96f54af129daa2771004ab771cecfe4f","datavalue":{"value":{"time":"+2014-01-22T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q390140$1E14216D-D307-4AC8-BBF2-0162A85F00DF","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"e4265a5412a56b6039db9291cd3f30418db99670","datavalue":{"value":{"entity-type":"item","numeric-id":247401,"id":"Q247401"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q390140$283A8C30-2753-4DF5-8D24-E423ECE1A814","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"2ce72165d993b0b8ed97728d731d2db2473b9554","datavalue":{"value":"65D18","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q390140$72B1B09F-4642-4529-B454-5DFAEAF8493F","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ea7da76f2f91b40a1ed0b11c5f2b399a2b66975e","datavalue":{"value":"6249151","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q390140$7D8BC70D-655D-4BAC-8FDD-542D557C907E","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9bd3b97137fc5cddeb53bb49b8b441b42d47d65a","datavalue":{"value":"triangulation","type":"string"},"datatype":"string"},"type":"statement","id":"Q390140$82FE9460-1ECC-4B41-B0DC-A32901366673","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c1a842b4f4882bc8cbc9e7e5ded22ca87149cc32","datavalue":{"value":"art gallery","type":"string"},"datatype":"string"},"type":"statement","id":"Q390140$496170C5-81D5-485B-BE6B-807C97799AF6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"35d4289385a4d9b393bae1b3a5dddcae4512592c","datavalue":{"value":"guarding","type":"string"},"datatype":"string"},"type":"statement","id":"Q390140$77A36201-56F9-46EB-84C4-8327D18FC548","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5b198546508854bcc521c452e3e0681a16812ba9","datavalue":{"value":"polygon","type":"string"},"datatype":"string"},"type":"statement","id":"Q390140$9363020C-B904-4AD6-9A89-B768750BFD3C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b911c3a7a8ca2246c1f84e7fe9a68eeb8e617f80","datavalue":{"value":"geometric algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q390140$6FC46AD1-9DB2-46D1-ACF1-7886764B61CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1fcef3f505b0e8640965af4a116d70dfa9d6d901","datavalue":{"value":"visibility-polygon computation","type":"string"},"datatype":"string"},"type":"statement","id":"Q390140$FD9C8F70-517D-402D-98DD-F057DBFA138C","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"7a5fc47b41131fc22c3c65e3289e155d42dec779","datavalue":{"value":"Q59782262","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q390140$53503C3A-41A0-4438-8658-B720E42C557A","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":"Q390140$2565C84F-0796-4FBF-9DBC-911F892E87FE","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"291b58ba106a1e0490a7c2bfea3c44c4b797c065","datavalue":{"value":"https://doi.org/10.1016/j.comgeo.2013.03.005","type":"string"},"datatype":"url"},"type":"statement","id":"Q390140$2CCA8D41-BF47-4471-9EBF-0E0A59610BD5","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"303f98e3db0c4db96707212d67cef3494504e995","datavalue":{"value":"W2086607663","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q390140$A9E92F29-38B3-43D8-A141-E09F8041B8E0","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b40f31b2ae3d298d424719ec6592ed9bc03ac1c4","datavalue":{"value":"10.1016/J.COMGEO.2013.03.005","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q390140$B1C53E48-E271-4258-BFC1-6D0E54433300","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"23ec5bbd137f4f43b928eb5a579b3a66e91ede99","datavalue":{"value":"Realistic input models place certain restrictions on the shape of objects fed to geometric algorithms. In this way unusual worst-case examples are excluded and complexity bounds might mimic the observed behavior of an algorithm more accurately.NEWLINENEWLINEThe authors propose \\(k\\)-guardable objects as a new model of realistic input. They remark that \\(\\varepsilon\\)-good polygons are \\(k\\)-guardable and show that their notion generalizes the notion of \\((\\alpha,\\beta)\\)-covered polygons (Theorem 1). Furthermore, they present two algorithms to triangulate a \\(k\\)-guardable polygon. The first algorithm is based on an involved subroutine, but does not need the guards as an input. The second algorithm uses visibility-polygon computations and requires the guards as an input. Both algorithms take linear time under the assumption that the number of guards is constant (Theorem 2, Theorem 3).","type":"string"},"datatype":"string"},"type":"statement","id":"Q390140$0D1E382A-85AC-4D0F-BD47-F142262BAE82","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"eb99754c51b5016c91ef2c93bb34832777a3c04b","datavalue":{"value":{"entity-type":"item","numeric-id":1405005,"id":"Q1405005"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"405ecd4d554c60d8d82704ff42b65e81ba75a7a9","datavalue":{"value":{"amount":"+0.779746949672699","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":"Q390140$B839B1FA-E4A1-49C5-93C6-1DABFCF49E33","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a086fff3318e32160cb89eee05cc23a897d5f353","datavalue":{"value":{"entity-type":"item","numeric-id":1005333,"id":"Q1005333"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5080b2e1766f417f9559656bd4a340846bfb6c40","datavalue":{"value":{"amount":"+0.7763529419898987","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":"Q390140$CFD724A8-0F12-4943-98F9-C52665F0E074","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"07005c95db27344f57933dde608c3df04d406c15","datavalue":{"value":{"entity-type":"item","numeric-id":1917042,"id":"Q1917042"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cd81cccf4d51bcc1794086f3553cee6f99c46a8b","datavalue":{"value":{"amount":"+0.7691176533699036","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":"Q390140$6FCE1750-37D4-43DE-B0C4-4776692B3906","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7523cb1fc950831f82f5fd5457bb142e74ad4f3f","datavalue":{"value":{"entity-type":"item","numeric-id":924091,"id":"Q924091"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cd87a1ca7a7220a3814383bf6cbe36ed0aa68ced","datavalue":{"value":{"amount":"+0.7566796541213989","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":"Q390140$0A7AA5D1-D5E9-4DE2-8D70-F281071A5B78","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1a42e79bc54b13bd01ad3d8c51de58040919fef1","datavalue":{"value":{"entity-type":"item","numeric-id":2375947,"id":"Q2375947"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8e85232144c490ad689d247d2d1ad745dce423d3","datavalue":{"value":{"amount":"+0.75298011302948","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":"Q390140$7BA214A4-2F62-44D4-9820-D8595B39A90E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:390140","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:390140"}}}}}