{"entities":{"Q1109582":{"pageid":1120331,"ns":120,"title":"Item:Q1109582","lastrevid":49210162,"modified":"2026-01-06T18:47:23Z","type":"item","id":"Q1109582","labels":{"en":{"language":"en","value":"The complexity of recognizing polyhedral scenes"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4070380"}},"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":"Q1109582$FEF52CFB-B059-43B6-B412-1E6FF369553C","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"63eaa38f1295e9c153b4bb3c16d2d6856a726182","datavalue":{"value":{"text":"The complexity of recognizing polyhedral scenes","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1109582$88B86B4E-70B4-42C0-905B-628A0636FB1D","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"45bb91405be1e4439998bb9f063dc08964a73598","datavalue":{"value":"0655.68114","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1109582$04A60BA4-2349-406B-9543-1A69460071FE","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"08a0fe9a03b7e110e2a9d923eb581612e7fb8c27","datavalue":{"value":"10.1016/0022-0000(88)90043-8","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1109582$7B56F458-7E2D-4DBC-BE95-B98DE6BD95F3","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"3114a9e7c18fd9d37962020c44023cd148b8085d","datavalue":{"value":{"entity-type":"item","numeric-id":215098,"id":"Q215098"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109582$3E465E3F-0D4D-4644-88D9-67460D1A6608","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"4703623e4fcbefcd3931d7b75f8faed8c58b1ed6","datavalue":{"value":{"entity-type":"item","numeric-id":222484,"id":"Q222484"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109582$76C6626A-AFFC-4B3C-95D3-6800C2807556","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"3340243f57e05f2265c56423c388055a14b114fa","datavalue":{"value":{"entity-type":"item","numeric-id":107189,"id":"Q107189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109582$B6CDC1F1-2CA5-4E8F-9869-76DAC29A33D4","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":"Q1109582$CAFA8A7C-9C86-4834-B922-87F2B4EE6D41","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"7c87f6bd265e8a00600cd91ab9a8e259ff4d2649","datavalue":{"value":"Given a drawing of straight lines in the plane, we wish to decide whether it is the projection of the visible part of a set of opaque polyhedra. This is the fundamental algorithmic problem that underlies much of the research in computer vision. Although there are extensive literature and reports on empirically successful algorithms for this problem and its many extensions, there has been no definite result concerning its complexity. In this paper we show that, rather surprisingly, this problem is NP-complete, and therefore there is probably no polynomial-time algorithm for solving it. This is true even in the relatively simple case of trihedral scenes (no four planes share a point) without shadows and cracks. Despite this negative result, we present positive results for the important special case of orthohedral scenes (all planes are normal to one of the three axes).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1109582$85E2016F-417A-447A-8948-550268F50DA5","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"8a784276b4e09d379c8147965411b455c3d79751","datavalue":{"value":"68T10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1109582$1E891751-C55D-4C71-B855-0EB71934ED4B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1109582$A3BF97C5-9899-4BA5-820B-67E4331E0F9C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"0e215620e372569550c5f2e635b83929a773bf8a","datavalue":{"value":"4070380","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1109582$21027534-4D24-4CC7-8CDE-BAC687C569C0","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4e2e01acbb88c1969db70a5034f47f3965b4cd61","datavalue":{"value":"polyhedral scenes","type":"string"},"datatype":"string"},"type":"statement","id":"Q1109582$FE233B76-593B-4D04-907C-57A672699BDF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6cc5918892b50010a90ee07fa121a8c66268a4b7","datavalue":{"value":"computer vision","type":"string"},"datatype":"string"},"type":"statement","id":"Q1109582$9D510AF2-F086-4B94-84F8-CD7FFA84D6C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f5498ca3e7abb035a7212a6e68902ac2f3c0126","datavalue":{"value":"NP-complete","type":"string"},"datatype":"string"},"type":"statement","id":"Q1109582$CAEFCD2F-D874-4869-9540-FE200BBB3B99","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":"Q1109582$A00FAB68-E86E-4B46-B6ED-3F3C1EE88CFF","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"292ea15aac1f68de3d279b40b551ea9d46f0f0dc","datavalue":{"value":"https://doi.org/10.1016/0022-0000(88)90043-8","type":"string"},"datatype":"url"},"type":"statement","id":"Q1109582$7F74270F-3231-4496-BD34-6FD7B5FF116D","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"860bec2f4e6811cc215313c63fc219e4d199684f","datavalue":{"value":"W1965915487","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1109582$6126A77F-7E3E-4A02-A489-E322BCE05125","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"77291d130a274d56065aac5859d2f2a62e2c614d","datavalue":{"value":{"entity-type":"item","numeric-id":4747544,"id":"Q4747544"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109582$371136E9-F76B-43D0-89C1-7988AAD7BEB3","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":"Q1109582$493F7F6E-B1AB-44B0-ADCD-8F2ABF34CCB7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1ab5fc1680050b62a8a279c6e9429126d023ccff","datavalue":{"value":{"entity-type":"item","numeric-id":1170895,"id":"Q1170895"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109582$F60C41C2-A400-43B7-8FFB-7134AF7EC330","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a134d979b2ba35c0547c297ea2d81f543924dbca","datavalue":{"value":{"entity-type":"item","numeric-id":2676557,"id":"Q2676557"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109582$2E9CE4C8-9783-453E-A966-B06A3966675F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5800d93eb4f8caa03263f0b51c3001208ff1e9ad","datavalue":{"value":{"entity-type":"item","numeric-id":3050157,"id":"Q3050157"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109582$E6BDEC09-7CD0-4A5D-88BD-D9BCCE59E391","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"176f92be0a5c8084cbea32a162c15c6e5a582bd9","datavalue":{"value":{"entity-type":"item","numeric-id":3936195,"id":"Q3936195"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109582$3E735580-F10C-4224-8BB7-E4F619DD583D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9ad86ed10f9dbc91aef6fdb78e5f6edf0ab2f5e6","datavalue":{"value":{"entity-type":"item","numeric-id":4739657,"id":"Q4739657"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109582$A747160B-1A5A-4B9B-9955-9CD1D123EFFC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6ba9b471781872e658d23c384f5e9706860bc2fc","datavalue":{"value":{"entity-type":"item","numeric-id":3732977,"id":"Q3732977"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109582$C3842432-9F14-4B11-8250-E5C8E798D757","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"88306911fb4cc0f4b76b7fe8486cc9c248d86996","datavalue":{"value":{"entity-type":"item","numeric-id":3727416,"id":"Q3727416"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"85022794beaa0c30780e6b2371f3b2d5752fa4e5","datavalue":{"value":{"amount":"+0.8448392748832703","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":"Q1109582$A9DC8256-8A5E-4176-98AE-3225AEAA26EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a831ff8988f2b190f1046e1a14a92b98e63da5ff","datavalue":{"value":{"entity-type":"item","numeric-id":2513326,"id":"Q2513326"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2d136fffcff0bb5e9bd5c22a4b70314d42d64c04","datavalue":{"value":{"amount":"+0.8412806987762451","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":"Q1109582$96DFC2E8-8479-4306-8051-68401FE323DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e4cf5f4a380e737777bda67071a1b2c3ba6788ef","datavalue":{"value":{"entity-type":"item","numeric-id":1274552,"id":"Q1274552"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1f4fc9baeda48a3846e4275f4b8f0ea237ee24b1","datavalue":{"value":{"amount":"+0.8237726092338562","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":"Q1109582$A3EEB010-7A95-48AC-BF2E-4A0E6F1FE462","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a5f4fd0bf14d28f1f53706ab27386f2e00fb924c","datavalue":{"value":{"entity-type":"item","numeric-id":798004,"id":"Q798004"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"188c6c993d8ead90da7333f1117ddf2408964f00","datavalue":{"value":{"amount":"+0.7929136157035828","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":"Q1109582$4CAEB0D2-8762-4476-851F-F8A9D480FCB6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f2b54812858cd033d7d288b3bf0115e314f94738","datavalue":{"value":{"entity-type":"item","numeric-id":5458852,"id":"Q5458852"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"17c8c236f0b2b4aa868f4d3b38840e5c8e1475a7","datavalue":{"value":{"amount":"+0.782509982585907","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":"Q1109582$4CD93104-472A-405A-9A25-E6DE14970647","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1109582","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1109582"}}}}}