{"entities":{"Q1182990":{"pageid":1193739,"ns":120,"title":"Item:Q1182990","lastrevid":66784983,"modified":"2026-04-12T12:50:40Z","type":"item","id":"Q1182990","labels":{"en":{"language":"en","value":"On the difficulty of triangulating three-dimensional nonconvex polyhedra"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 32573"}},"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":"Q1182990$CD1907E9-C8CA-4C12-A41D-5191A3814E8E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"765f257f5b00b61f0a29b53bd4b83c1c2d5601b8","datavalue":{"value":{"text":"On the difficulty of triangulating three-dimensional nonconvex polyhedra","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1182990$E57AEC6F-2A50-4B0C-9BFB-B978DB773652","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"7a1496e70c8e5e73345f3a8b9665f5dfeba58119","datavalue":{"value":"0747.52009","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1182990$2310E32D-7A44-4097-9771-2F556AA06836","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"e698440a706735f1b631f98518e003d73700c384","datavalue":{"value":"10.1007/BF02187840","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1182990$356FB85E-42D7-417F-A5A6-039ABE8AE1B2","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"6b75acc11e6e5604834e33a66044f2cec7caf6ab","datavalue":{"value":{"entity-type":"item","numeric-id":1182989,"id":"Q1182989"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1182990$7C43F652-B5F1-4DF7-9FB3-4DDA837B8A93","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"b616ea83f16323d1b4f0e42f503e6129370f5d6d","datavalue":{"value":{"entity-type":"item","numeric-id":686136,"id":"Q686136"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1182990$D3A5E87C-2E2B-4C9B-8D00-1F72935644CA","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"b6f367138a9ac2b85113cfed5a6fd5bedcc8944c","datavalue":{"value":{"entity-type":"item","numeric-id":178842,"id":"Q178842"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1182990$90A2FFB9-796F-406E-A358-097178C16596","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"120787504bea9565def539fb4bfb19084956028b","datavalue":{"value":{"time":"+1992-06-28T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1182990$5644FEBE-4CBD-4AAD-9F3B-064A44605EA6","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"01da3182579df3876f369d2d74fca72d86276ef4","datavalue":{"value":"https://eudml.org/doc/131194","type":"string"},"datatype":"url"},"type":"statement","id":"Q1182990$EF0C12A6-0064-4C4C-AC73-0995CB3F7D6C","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"d182b83bc472c868855d38bae7c6fd6767ce7c43","datavalue":{"value":"It is well known that for a given 3-dimensional nonconvex polyhedron a decomposition into tetrahedra without additional vertices (= a triangulation) is not always possible. A twisted prism provides a counter-example. The authors consider the algorithmic question how to decide whether a given 3-dimensional polyhedron \\(P\\) is triangulable or not. It turns out that this problem is \\(NP\\)-complete even when restricted to the case of star-shaped polyhedra. More precise it is shown that for each Boolean expression \\(E\\) there is a polyhedron \\(P\\) such that \\(E\\) is satisfiable iff \\(P\\) can be triangulated. The construction of such a \\(P\\) makes use of so-called ``niches'' which are twisted prisms attached to a given polyhedron and which restrict the possible triangulations in a very effective and controllable way. If one allows additional vertices (Steiner points) then the problem turns out to be \\(NP\\)-hard if the number of such points is at most \\(c\\cdot n^{3/2}\\) for an \\(n\\)-vertex polyhedron.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1182990$A6129753-FD46-48A8-AAF3-F2BE20292EB7","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"58b4807eed7efcfa542a55961c60a6e11dd70fd1","datavalue":{"value":{"entity-type":"item","numeric-id":1163256,"id":"Q1163256"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1182990$9E417F6A-B4A2-4A2A-951A-0108143DC47A","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"2762df744fec88c5da60f696833f02907bd4417a","datavalue":{"value":"52B55","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1182990$4381A948-76FD-4844-8F4C-EB9CC6AE1B9F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5ae9e2988e76d371f7e87b79bcd004ea2b80f64","datavalue":{"value":"51M20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1182990$B1C47951-E3E4-4180-AFA1-7DAFDC4484CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1182990$5EA4DA07-2AF0-488D-8AC2-11142100140A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"719fd2949b80c8cc7a58cbc4ca1d7d0d3b69123f","datavalue":{"value":"52-04","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1182990$2805CB85-961B-4247-B3AA-5AE01BB02AEB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1182990$5F3FBFF8-AD86-480B-8595-BE5577F6D21E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1de3565cfd3393000dd87ca545f95ff84d4c1446","datavalue":{"value":"68W10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1182990$4B9E042B-CBE7-4C81-811C-FE3011BF823D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"9ab8f3fbac1b2afd41284e72b161fc32fe50eb67","datavalue":{"value":"32573","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1182990$48E56FF2-E576-42B9-8DA0-95F43EB00115","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"77e401ec50a8cee9ccceb3304e2efdab6f0af9a9","datavalue":{"value":"partition of polyhedra","type":"string"},"datatype":"string"},"type":"statement","id":"Q1182990$8EC40594-ECD2-450D-926A-5357C28E9EEF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3658c6d8ce6ebdf249b8f73c258a6a15cf3fca90","datavalue":{"value":"triangulation problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1182990$CDF367AC-3669-4626-872F-999756B097AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ccb18d89fbb3fc8685d6aeab858e5b2c1955c144","datavalue":{"value":"3-dimensional nonconvex polyhedron","type":"string"},"datatype":"string"},"type":"statement","id":"Q1182990$9236159D-1180-4A8D-8067-F7F76AB33DA4","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":"Q1182990$A85D018B-5CAD-4D48-8400-6ACC03674BC4","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"5e3073e172f376bebfbcbf8abcdab5c2b61c5acf","datavalue":{"value":{"entity-type":"item","numeric-id":1820437,"id":"Q1820437"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1182990$BBC63710-35DA-450F-B8DF-9056BE96838D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fea3dd79aeafd34f7474e9dd85223781a1b1cf9e","datavalue":{"value":{"entity-type":"item","numeric-id":3355233,"id":"Q3355233"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1182990$0C2A644B-891C-4F2E-9951-E3E157DC3A73","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"772959591e41b4b2a2b1af0c54b743acb1e5b4f3","datavalue":{"value":{"entity-type":"item","numeric-id":914375,"id":"Q914375"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1182990$F454F82E-89BA-46FC-8A81-231682153498","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"63159cb6576360b5354e7cf2ead46ee21dc26ab4","datavalue":{"value":{"entity-type":"item","numeric-id":4304059,"id":"Q4304059"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1182990$75CAB439-D949-4EB1-8D18-48232A0D60AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"291432c035296227f4fa36821b7ced64a966932a","datavalue":{"value":{"entity-type":"item","numeric-id":2638826,"id":"Q2638826"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1182990$E2627A76-366C-42F0-A538-B8120B0705F4","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":"Q1182990$AEEDED2A-0921-4F58-96A8-85CFCCD4D344","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a75892efb8c423df4e08c3a2522f9c8641bb850b","datavalue":{"value":{"entity-type":"item","numeric-id":3799261,"id":"Q3799261"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1182990$8F12165E-2FA6-4A7E-8D76-58529A615D16","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"927dbf1a3adb1e111bc0c56e1db86cdcead56ead","datavalue":{"value":{"entity-type":"item","numeric-id":3967065,"id":"Q3967065"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1182990$E42CCA90-18FD-43F6-B56F-9DC4B0354588","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"694910451200ab7067ebbccacf142af3ac2a2369","datavalue":{"value":{"entity-type":"item","numeric-id":3992847,"id":"Q3992847"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1182990$53E40D57-C5C7-4BE5-BCF9-150C9C56404C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"44c6e0ce4894119016cc0f94d0e5723742399a91","datavalue":{"value":{"entity-type":"item","numeric-id":3911698,"id":"Q3911698"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1182990$D98E56F5-954F-43B6-B676-2F4A39ACA70D","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"849e4ce41a7dcf7cb51eb37b7e09f3476f9cb96e","datavalue":{"value":{"entity-type":"item","numeric-id":1392846,"id":"Q1392846"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"221a06fea7c483193370047386c975ad4082e3ef","datavalue":{"value":{"amount":"+0.8888348937034607","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":"Q1182990$538824ED-900E-4F70-B35F-8CF61CBCCDA1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4eeffd098169ffabe66df96426e491e744cdd7be","datavalue":{"value":{"entity-type":"item","numeric-id":5114888,"id":"Q5114888"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b8e8afabecb11039916a1cd1e6b4df1bc45674ba","datavalue":{"value":{"amount":"+0.8408688902854919","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":"Q1182990$0ACC9406-34B5-408D-8B9D-CE2DAD18FDF7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6bf4a2640974164a3e99e11ee6facc2c78c71fdf","datavalue":{"value":{"entity-type":"item","numeric-id":914375,"id":"Q914375"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6f5f7114409654d7b053ca097743faf3bdf7d8f4","datavalue":{"value":{"amount":"+0.8374595642089844","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":"Q1182990$1F94493C-F56D-4737-950C-BE39BAA1115A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9c4fed6f5cf5a9ce9d205951579dce6a3696ea4f","datavalue":{"value":{"entity-type":"item","numeric-id":2708044,"id":"Q2708044"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"eeb72aa396410822e800163b1f04b29928aeb877","datavalue":{"value":{"amount":"+0.8309447765350342","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":"Q1182990$1FE0D8B3-8278-47B2-A3D4-6C28A8A888D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"875eda4920a2e6d3201575c32270738938c4b651","datavalue":{"value":{"entity-type":"item","numeric-id":5057423,"id":"Q5057423"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"02519972f78a3d6ff44d00162f04a2fc497f005a","datavalue":{"value":{"amount":"+0.8202533721923828","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":"Q1182990$56E6BEFA-33E1-44CA-9CF3-4DC8EF597D7C","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the difficulty of triangulating three-dimensional nonconvex polyhedra","badges":[]}}}}}