{"entities":{"Q1114398":{"pageid":1125147,"ns":120,"title":"Item:Q1114398","lastrevid":49238320,"modified":"2026-01-06T20:11:25Z","type":"item","id":"Q1114398","labels":{"en":{"language":"en","value":"An \\(O(n^ 3)\\) algorithm for finding the minimal opaque forest of a convex polygon"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4082971"}},"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":"Q1114398$055F37BF-77E2-4CD6-A235-0F8EFC8633FD","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c12f65efe15786364a202789ccda8872bd22a899","datavalue":{"value":{"text":"An \\(O(n^ 3)\\) algorithm for finding the minimal opaque forest of a convex polygon","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1114398$9991C265-B0A0-4C14-97C2-506A0E7F9F5D","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"5818b6829e94c32f9b8306a16212f79a876f8365","datavalue":{"value":"0662.68040","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1114398$CD1087E5-A3A6-469D-9C2D-00ADE7B19FC9","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"1a1152e04926917e1e3945cd6ac2dcd02a12c2db","datavalue":{"value":"10.1016/0020-0190(88)90122-6","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1114398$1F4E986C-BDF7-4008-BACD-F5476B504AEA","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"45e088ec4c0d3443b53b0214708b2e73684b307c","datavalue":{"value":{"entity-type":"item","numeric-id":918704,"id":"Q918704"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1114398$B64F3F2F-D38F-48BD-9F08-BE0432FF85C9","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52fa7d44b58d0511cb8993765bd916aef86052d8","datavalue":{"value":{"entity-type":"item","numeric-id":63092,"id":"Q63092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1114398$AF4BB483-4D8D-4618-9A1C-FD4236969660","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"31a1937240ca4a323604b4728c31d242b5596d7c","datavalue":{"value":{"time":"+1988-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":"Q1114398$C3008F12-86F1-4F6D-8F94-A8F1A874B8DA","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"398549aa2a7605f976c1a5376aa01d47c4dc8859","datavalue":{"value":"An \\(O(n^ 6)\\) algorithm for computing the minimal opaque forest of a convex polygon has been proposed by \\textit{V. Akman} [ibid. 24, 193-198 (1987; Zbl 0653.68030)]. We show that a simple modification improves the running time of this algorithm to \\(O(n^ 3)\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1114398$24C26F49-6F0E-4FA6-9AAE-F1F5FB17E521","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1114398$FA55DAB9-0E54-4AB4-87F6-E55DE97BB6AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1114398$B8C2AB07-A998-40BE-853F-C138F81BBC71","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e5762e9b09407c15760c5fa5cac71c82c32bf230","datavalue":{"value":"52A10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1114398$20A35052-B8CB-430A-9E94-5B5DAAAA1D6C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"e40192e93a582473c246a5060316092181cb4642","datavalue":{"value":"4082971","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1114398$D64FBFEE-8576-46F5-8E81-CC0B4C28A9C6","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"551d108313cfab3a77b395a647aede7021169ebd","datavalue":{"value":"computational geometry","type":"string"},"datatype":"string"},"type":"statement","id":"Q1114398$1E4C984B-4ACC-4C59-AA7F-E023F14C5DB4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c423252012c4c6732b4c43e6a338efae7d2cd1fc","datavalue":{"value":"minimal opaque forest","type":"string"},"datatype":"string"},"type":"statement","id":"Q1114398$9EF00ABF-ECCC-498D-A258-17DE892C5749","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7638652825683bfe9fbdcacf89d6fa0bde32cc7a","datavalue":{"value":"convex polygon","type":"string"},"datatype":"string"},"type":"statement","id":"Q1114398$4A2267AF-56B2-4DE2-B18C-C06942863672","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":"Q1114398$34B19B6A-63EB-484F-8494-D1AF99817636","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"17dd1707ae4b14cdea9eb14be3b7c838109c3804","datavalue":{"value":"https://doi.org/10.1016/0020-0190(88)90122-6","type":"string"},"datatype":"url"},"type":"statement","id":"Q1114398$F871B661-A494-4F8C-A2E6-BFFBF4A42455","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"9dc6b6568f5dd8acff68ab1f8680bd93d16e7703","datavalue":{"value":"W2058215634","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1114398$E437E0F4-ED37-462B-8001-888CA1D8577B","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"599971b482668e6c9533ba7beec94ccd8071b504","datavalue":{"value":{"entity-type":"item","numeric-id":1107998,"id":"Q1107998"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1114398$41DA06EA-5FF3-41D1-85C5-4E526550B510","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"55b602c669ee6a5a9981bd24d61e6f87aba0c852","datavalue":{"value":{"entity-type":"item","numeric-id":1107998,"id":"Q1107998"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f2e7ea8e483e60503f90182dec635dc322e799e8","datavalue":{"value":{"amount":"+0.9131844639778136","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":"Q1114398$18E8F516-A75D-423A-B7E9-2E2CF2615431","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2d580b8a55e2dda7dd9d473bf1db1f7bab521012","datavalue":{"value":{"entity-type":"item","numeric-id":1183430,"id":"Q1183430"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"eef307146071225a025ce794835901cb34d3d4cd","datavalue":{"value":{"amount":"+0.884669303894043","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":"Q1114398$E908DFA1-0F4A-4D59-94C5-CCA2BB87E896","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3e112832efca1b7ffd98ab0695766e8cbec48871","datavalue":{"value":{"entity-type":"item","numeric-id":4326861,"id":"Q4326861"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9b1a34c61e6b07f44e3239bf6389ac5f1c0eb626","datavalue":{"value":{"amount":"+0.8795388340950012","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":"Q1114398$3C68CF0B-A72C-4106-A398-04FCFDE659D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dffc900d7da51582ab80cd161019fd1ceb3bb1ee","datavalue":{"value":{"entity-type":"item","numeric-id":3088094,"id":"Q3088094"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5bea724ee08077d72221da3d06a01b36a041fe14","datavalue":{"value":{"amount":"+0.7975576519966125","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":"Q1114398$42770D4C-7D6A-457A-A08A-E03E770595D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"577438e0eebfd38fca7d76c7095757b6045c68c3","datavalue":{"value":{"entity-type":"item","numeric-id":517796,"id":"Q517796"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f04fb5c9e7072090cd746a86baf1f061eee937a9","datavalue":{"value":{"amount":"+0.7925097346305847","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":"Q1114398$44B6BFA3-F7F5-4961-9E39-DF15E415FBC2","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1114398","badges":[]}}}}}