{"entities":{"Q1328388":{"pageid":1339138,"ns":120,"title":"Item:Q1328388","lastrevid":67180179,"modified":"2026-04-12T15:50:20Z","type":"item","id":"Q1328388","labels":{"en":{"language":"en","value":"A note on hyperplane generation"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 599864"}},"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":"Q1328388$305BCEB4-485F-4699-BA5E-880E12EC089D","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ad907163b7236cd599bbc479dc1cb709f99d8e88","datavalue":{"value":{"text":"A note on hyperplane generation","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1328388$5BF86150-4AD6-4D89-890B-B7823EF4B2BB","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"fe8b141aab78647314955cbc77bcb0ca69fe51fa","datavalue":{"value":"0803.05015","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1328388$59C80274-1C1F-4B58-9394-613F40B208C9","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f07f6fd6d97bd24ff86249abf8a501d3b63b437d","datavalue":{"value":{"entity-type":"item","numeric-id":256978,"id":"Q256978"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1328388$277710AD-87F3-443F-949F-7DFA6EA0F108","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"6fec002a86967a3d68ab1d50269b51e2d2e883c0","datavalue":{"value":{"time":"+1995-01-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":"Q1328388$01E88286-D9C7-42A4-821B-32591AB2BDAB","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"b1e7b56e57babc72f09e15c78a4db66ff103def5","datavalue":{"value":"This short and elegant note describes an algorithm that generates all the hyperplanes spanned by a finite point set \\(X\\) ``at a polynomial rate''. That is, although the set \\(\\mathcal H\\) of hyperplanes may have exponential size, the first \\(i\\) hyperplanes in \\(\\mathcal H\\) are generated in a number of steps that is polynomial in \\(i\\) and the size of the input. In particular, one can check whether a given list of hyperplanes is complete, in a time that is polynomial in \\(| X|+ |{\\mathcal H}|\\), the number of points plus the number of hyperplanes.   The proof is based on a matroid formulation of the problem: ``The introduction of matroid theory here is just for clarity and maximum generality, but later, in the proof, the use of matroid theory is essential.''   A problem of Lov\u00e1sz that motivated this note, how to check whether a list \\(\\mathcal H\\) of hyperplanes completely describes the convex hull of \\(X\\), remains open.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1328388$DCE9C128-B035-4CDE-9FCC-A176F3EEEEC7","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"a06727f99c93aa58e84e3d476d4f6a1bed523458","datavalue":{"value":"05B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1328388$6F967731-72F7-4670-ABBB-DBA0CD0A0D6C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"7501cba48320d715aa2f92c8f7803347a8901b66","datavalue":{"value":"52C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1328388$4ACF9F42-BDBB-45DC-96EE-065730BA4449","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d9a4e87e0b277ee660224a228349fc9d12e578db","datavalue":{"value":"52B40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1328388$FA032C97-705B-4B50-8C78-A70D485E3DC2","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c210c9252f6687efd78ea1e86cc647080eff0679","datavalue":{"value":"599864","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1328388$52A629CB-8961-4796-91DC-F19766B83AE7","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4f4607e63a3408b0f4d54243f825ed55841bbe17","datavalue":{"value":"point configurations","type":"string"},"datatype":"string"},"type":"statement","id":"Q1328388$2187F388-7D77-48E7-85CA-A5318B157707","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a39ec4307b26d786312cb390856b9060d3bf22c8","datavalue":{"value":"matroids","type":"string"},"datatype":"string"},"type":"statement","id":"Q1328388$B6BED030-3C56-4CBD-9F32-44215FBB45D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4bec5a18bb20ed807e3b719a721947e75879c156","datavalue":{"value":"hyperplane generation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1328388$E0FD7430-1CB7-4698-B45A-EF7D68889F05","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"caf0b04816dae42dfdc9df79557fa5d0d33914b4","datavalue":{"value":"independence oracle","type":"string"},"datatype":"string"},"type":"statement","id":"Q1328388$A0B6CB2D-E69F-4712-A2BE-3B50B5D18D52","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4227852808f0bca24187d7c6031ee4347a25f7f1","datavalue":{"value":"matroid algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1328388$09B1ABDA-243C-4875-9E07-13E7FBD66B33","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"6b7666b1aea36d852e5d73efdf8f9faa64e3f54f","datavalue":{"value":{"entity-type":"item","numeric-id":705887,"id":"Q705887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1328388$76EE8983-543C-4275-A752-51D00F0A400C","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"2a414f06c82d770f131a5979daa1aa099bf5faff","datavalue":{"value":{"entity-type":"item","numeric-id":189313,"id":"Q189313"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1328388$72E00420-D61A-4A5B-95FA-604656992CB2","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":"Q1328388$73DE761F-A902-4C40-852B-56782543EFE9","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"e3b0d65236e607f2cc80c792ee1f814c62f5982b","datavalue":{"value":"https://doi.org/10.1006/jctb.1994.1033","type":"string"},"datatype":"url"},"type":"statement","id":"Q1328388$CCB1F9F4-907C-4F91-BE84-31DF33022367","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"a77632db2d2da09ca451ca94ff167f1aefa0e2cb","datavalue":{"value":"W1993486814","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1328388$1EFC1CC3-42A8-401A-B838-E0DA3AD21C84","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"4e98600eb51dcf826e1a8a6c87b12ac4a8ea81bc","datavalue":{"value":"10.1006/JCTB.1994.1033","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1328388$F5B2FEC5-5806-4209-B13D-22D69B972E4A","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7adc084fb51fa4cb988978b58714460d8be0cc9e","datavalue":{"value":{"entity-type":"item","numeric-id":3740283,"id":"Q3740283"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"be3dffbcce8d781cd977796535b48042d02529c1","datavalue":{"value":{"amount":"+0.7414335608482361","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":"Q1328388$B99B1EB8-EDF2-4C57-9CDD-9E3C6E4EF5C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2120375ce96dc2f245210d1cc717a39345623f6d","datavalue":{"value":{"entity-type":"item","numeric-id":5054865,"id":"Q5054865"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1fe5e901d2f09ce10d08448abbdbfd0f7f8a3175","datavalue":{"value":{"amount":"+0.7172130346298218","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":"Q1328388$91CA8DC7-9028-495C-AD0A-51F239D9CD5A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"12a14ae25319f41db838ccbdd1ec14c5a3b92e0c","datavalue":{"value":{"entity-type":"item","numeric-id":4719331,"id":"Q4719331"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bd0f4ce311b4bd3c1b8597577037636921890fcf","datavalue":{"value":{"amount":"+0.7159651517868042","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":"Q1328388$8076EF55-D387-4631-88FD-61C39306FF39","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a12989eb2e81b129add69d69a33c9145f691ccdc","datavalue":{"value":{"entity-type":"item","numeric-id":1209837,"id":"Q1209837"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e3ef390cab9945bc941ceef98b08a9a8cba9f393","datavalue":{"value":{"amount":"+0.7135465741157532","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":"Q1328388$AA0FC0E8-AF1B-44D4-BD27-E393DFC4A362","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"26ee1634e5817eac5c0b470a327cafbad95c5bf7","datavalue":{"value":{"entity-type":"item","numeric-id":4401009,"id":"Q4401009"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"882bc0e108c5dc05b4499beab6b7473810454d66","datavalue":{"value":{"amount":"+0.7125897407531738","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":"Q1328388$4D162234-C8DF-40BD-8871-885D9A415723","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A note on hyperplane generation","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_note_on_hyperplane_generation"}}}}}