{"entities":{"Q958243":{"pageid":960091,"ns":120,"title":"Item:Q958243","lastrevid":50515799,"modified":"2026-01-14T06:33:52Z","type":"item","id":"Q958243","labels":{"en":{"language":"en","value":"On the hardness of computing intersection, union and Minkowski sum of polytopes"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5377165"}},"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":"Q958243$2DF49F63-8B55-4F23-9000-2594A6335AA5","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"fad764b6d29d308231cd442242fab797f824c9a8","datavalue":{"value":{"text":"On the hardness of computing intersection, union and Minkowski sum of polytopes","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q958243$0EFE41CB-6486-4767-AC46-03DAF64597D9","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"d12e33c9b96b4f5746810ec2c7bc554a5265dde9","datavalue":{"value":"1155.52008","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q958243$718FDCA1-ADD5-4AE5-A2F4-5A92F7E6CD1C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"7cd8238ea275ad1f712fee23b00be1e92331fd1c","datavalue":{"value":{"entity-type":"item","numeric-id":450532,"id":"Q450532"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q958243$EC7FF9EA-D78A-43DF-BD9A-FA95548DD769","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":"Q958243$AF6296C9-E3D8-4A03-9E9C-0D3C76B80695","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"c7e93f8d3c28f11b076aa7adf47edebc135f21d9","datavalue":{"value":{"time":"+2008-12-02T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q958243$C31C69B9-C4D3-4F7B-B01B-55BECB302A1C","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"718ab5607b219c04a8537868d67a1c025a7141e1","datavalue":{"value":"For polytopes \\(P_1\\), \\(P_2\\subset \\mathbb R^d\\), the author considers the intersection \\(P_1\\cap P_2\\), the convex hull of the union \\(CH(P_1\\cup P_2)\\) and the Minkowski sum \\(P_1 +P_2\\). The principal aim is to analyze the algorithmic complexity of performing these operations and providing a nonredundant description of resulting polytopes. For the Minkowski sum, it is demonstrated that enumerating the facets of \\(P_1 +P_2\\) is \\(NP\\)-hard if \\(P_1\\), \\(P_2\\) are represented by facets, or if \\(P_1\\) is specified by vertices and \\(P_2\\) is a polyhedral cone specified by facets. For the intersection, it is demonstrated that computing the facets or the vertices of \\(P_1\\cap P_2\\) is \\(NP\\)-hard if one of \\(P_1\\), \\(P_2\\) is given by vertices and the other by facets. Besides, computing the vertices of \\(P_1\\cap P_2\\) is \\(NP\\)-hard if \\(P_1\\), \\(P_2\\) are represented by vertices. Because of the polar duality, similar results hold for the convex hull of the union of polytopes.","type":"string"},"datatype":"string"},"type":"statement","id":"Q958243$E5D3971D-3669-4E26-9AD4-0FB23BCFF103","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"798eea1f37baf19c7c9678fe1fc9dd8eadfa6f52","datavalue":{"value":"52B11","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q958243$FEA895F5-76C2-4243-B0A9-D890C2FDDC2B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"78931806833c54190437f3675cf624ba3d256107","datavalue":{"value":"52B05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q958243$1D556FB4-2158-42EB-9069-06F13539B284","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q958243$96A22DDD-CE38-4686-BD0E-86265150F5B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"36d142e7ea03446b1d7deb9627eedb9f0297f86a","datavalue":{"value":"90C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q958243$F0385AEA-77DC-4236-86FD-D6687F89CE30","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"4e77111d6447cff728625be2237bc70e5555cf6e","datavalue":{"value":"5377165","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q958243$F04413FB-CDBF-4671-AA88-726B45B717A9","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"756a92de806600ccd2ff23166271ffd1eef41605","datavalue":{"value":"polytope","type":"string"},"datatype":"string"},"type":"statement","id":"Q958243$7ACD558C-D9EF-4CB1-8E00-60AED79EBBA5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"98a64966f1cdfab6bed6b3dcc04c8f9e4a917c98","datavalue":{"value":"Minkowski sum","type":"string"},"datatype":"string"},"type":"statement","id":"Q958243$920FC824-E821-41CA-9A6C-8737302D6C55","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"697626a6c5ea4a7921eba4e0f3fdba17e2e290d9","datavalue":{"value":"convex hull","type":"string"},"datatype":"string"},"type":"statement","id":"Q958243$D892AC52-7A34-46DD-A000-59E8FD3E2FD1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"22f51dbd083a4570773d5dfb4907a41404745e53","datavalue":{"value":"Turing reduction","type":"string"},"datatype":"string"},"type":"statement","id":"Q958243$E236B6C6-4898-4E1A-BED0-E214568CB012","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"295338818b68d8df51ee6090af1d70fb07b08753","datavalue":{"value":{"entity-type":"item","numeric-id":554155,"id":"Q554155"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q958243$A70C637E-1B20-42C5-9C55-B4D055A65F68","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":"Q958243$CC3B4642-1CF6-4879-9753-156324E81D3C","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"e1f64c905d6aa8c931df49ba6310fd452c12597b","datavalue":{"value":"https://doi.org/10.1007/s00454-008-9097-3","type":"string"},"datatype":"url"},"type":"statement","id":"Q958243$42DFD1E3-3B14-4040-B84A-3E8EAE136992","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"398606f1a5118320cdde209b3247202ef44867ba","datavalue":{"value":"W2000147742","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q958243$4A09158E-33B2-46F9-ACBD-83C9EBEF407E","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"1776ffcd23318a03778deb65a3ef6ce3fd7c7ce3","datavalue":{"value":{"entity-type":"item","numeric-id":1356937,"id":"Q1356937"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q958243$33BC983B-BBB6-4BA8-B516-256E9CBAFDAC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"477472125047662488d35f63e8eeef0d620af231","datavalue":{"value":{"entity-type":"item","numeric-id":1115345,"id":"Q1115345"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q958243$2AAE4890-5643-4EF6-A2A7-8E8035F7E9AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fe452d3e0b604ad7b5e11712653a2188210b8ff1","datavalue":{"value":{"entity-type":"item","numeric-id":3703587,"id":"Q3703587"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q958243$B54119E4-F99B-4B0E-8FCE-857BC8D21461","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4f1db4d45b5df18eaf8105486da53bf5dcb7718e","datavalue":{"value":{"entity-type":"item","numeric-id":2643562,"id":"Q2643562"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q958243$2E28DA0A-5245-44DE-838A-38427F3C2635","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a5e8820cd01a5ae9be1a21334372c7c31573a1cc","datavalue":{"value":{"entity-type":"item","numeric-id":5952968,"id":"Q5952968"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q958243$8E73799B-D1F4-4BC1-BB2D-17E14B195F22","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"abc9e031c94368a9b2650ef739589202f91e7974","datavalue":{"value":{"entity-type":"item","numeric-id":2369928,"id":"Q2369928"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q958243$72CECDA5-796D-4B20-8D01-9A5BC262A4D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8e64098d7a3f9ba0263d98df401722c77cb8e768","datavalue":{"value":{"entity-type":"item","numeric-id":4695386,"id":"Q4695386"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q958243$67A99B82-3631-4DAB-8C98-4CAD4CA06A07","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a8c9ee08bf2113ff3da12debab83a452160edd63","datavalue":{"value":{"entity-type":"item","numeric-id":1309040,"id":"Q1309040"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q958243$BA9A7A2A-20E8-4F52-980D-897B4ABD56D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bb36df73a03f449f5e819e41d24c4099708bbd4b","datavalue":{"value":{"entity-type":"item","numeric-id":4434671,"id":"Q4434671"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q958243$47EB36E8-AD0E-4A08-B8BB-1E7643624B6C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2b51adb31a458ba788306ba147c52c7a8b7cb2e4","datavalue":{"value":{"entity-type":"item","numeric-id":1572873,"id":"Q1572873"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q958243$9B9C6BFE-E367-447F-AAD2-BB1AF731DB75","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"00bb7591b2f22096ba7a92a7108ed37c133fd741","datavalue":{"value":{"entity-type":"item","numeric-id":5920505,"id":"Q5920505"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q958243$285B6A26-7CD3-4337-A186-0DBB1F4C7BCA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"97236fbeb6b6b2bba840114a8ba2f0448b9619f9","datavalue":{"value":{"entity-type":"item","numeric-id":4197641,"id":"Q4197641"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q958243$D99FDBDA-8A82-4CB9-842C-0137BBA28372","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d6df239e965f248c39368523a1619935f9d684a6","datavalue":{"value":{"entity-type":"item","numeric-id":1321592,"id":"Q1321592"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q958243$05D6D7C0-9B1F-45F9-9A00-AAE2335936D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8c60deea7785192df8a7cf25a408140a2f317a6c","datavalue":{"value":{"entity-type":"item","numeric-id":4953977,"id":"Q4953977"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q958243$413CF9FA-AF32-4AA1-96D6-66B990A2563D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5ce2a67917373e5b4e39d7c86d75e3ad261de966","datavalue":{"value":{"entity-type":"item","numeric-id":4323295,"id":"Q4323295"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q958243$894D9FA9-3DC7-4832-9CE6-DF14C616E786","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"9741d88a36b1007adee2862ee6ac9bba3f19f2a4","datavalue":{"value":"10.1007/S00454-008-9097-3","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q958243$33388137-A1DA-4C59-AE93-584E68429060","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ae765272e97060d60edffe6e90d924ed569321f4","datavalue":{"value":{"entity-type":"item","numeric-id":3602888,"id":"Q3602888"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"365f282dab703ce5bad104f4c196ff9d5b133c29","datavalue":{"value":{"amount":"+0.9311149716377258","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":"Q958243$A6ED11DA-E8E5-4471-A3B4-F5B8B4866B12","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"81ab362da082230b9d0abeec55b1eb9287d98ab6","datavalue":{"value":{"entity-type":"item","numeric-id":5943314,"id":"Q5943314"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4be19ec68858114031e4e4d00891315bc8ad8ea0","datavalue":{"value":{"amount":"+0.8045080304145813","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":"Q958243$3CDCC2C1-3F68-458D-91E0-731F9C0422F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"061ec65d3a6847ba3b7817f1e9e81715a2173407","datavalue":{"value":{"entity-type":"item","numeric-id":4863381,"id":"Q4863381"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a12086e86ab78b44044a1e7fd23a93d4c4dc87b1","datavalue":{"value":{"amount":"+0.7770888209342957","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":"Q958243$A60FF17B-44FF-474A-83EF-74BB51121008","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"58fd6e9018459fa770e30e02f82cdc53185de47b","datavalue":{"value":{"entity-type":"item","numeric-id":1356937,"id":"Q1356937"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"04de690ad79ebeb026e408ff219e583e16dca4fe","datavalue":{"value":{"amount":"+0.7769099473953247","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":"Q958243$9E433EE3-4DA8-4A5E-B1A7-2175B02FD35A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6ac003367c70af4dd31151482c26e85a66c9bd48","datavalue":{"value":{"entity-type":"item","numeric-id":3832046,"id":"Q3832046"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d33b211a79ea0870320c6f00e6326bc01845537d","datavalue":{"value":{"amount":"+0.7746734023094177","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":"Q958243$3CAA0452-8813-4D6E-9C4E-F37DCD7813C4","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:958243","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:958243"}}}}}