{"entities":{"Q919829":{"pageid":921677,"ns":120,"title":"Item:Q919829","lastrevid":49412071,"modified":"2026-01-07T03:01:21Z","type":"item","id":"Q919829","labels":{"en":{"language":"en","value":"The upper envelope of piecewise linear functions: Tight bounds on the number of faces"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4162269"}},"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":"Q919829$A48A1633-3F6B-48A3-9BFD-553954CAAA9A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"dc6f4d7b3eca8a8ca38aa14edd1fb54642257b33","datavalue":{"value":{"text":"The upper envelope of piecewise linear functions: Tight bounds on the number of faces","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q919829$5A00DF4E-B179-4AF5-AA35-5CD8393B324A","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"861311a6b9d07c9e1bcfccb29fab1beb4612831a","datavalue":{"value":"0707.68043","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q919829$32FC3359-30E0-4A3F-9CB8-35E7BE0483F2","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"1f32e05332b394123df56841d77805704390a3e8","datavalue":{"value":"10.1007/BF02187734","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q919829$4CF29F09-2B11-41D0-A3E8-D8CB02B72E81","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"a06f7d76e1dbfa89a80e5d40561052d9e137ca58","datavalue":{"value":{"entity-type":"item","numeric-id":242843,"id":"Q242843"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q919829$7ACF1733-485C-4F7A-92F3-CA647D658CA8","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":"Q919829$58FE2ABD-1B34-40EF-AAB3-46E640098D56","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7211ad5ca16eb0d22cd0051fff3d0f3af254ceb6","datavalue":{"value":{"time":"+1989-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":"Q919829$C9E12A92-73C5-49FD-8C95-EFE6B698A46B","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"8bb3b0e2d8bd629f17833cdc9c974351838cfefe","datavalue":{"value":"https://eudml.org/doc/131083","type":"string"},"datatype":"url"},"type":"statement","id":"Q919829$95B3FC77-BC4F-4DB5-BBE3-AA03B395C71F","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"5fd7b87296769e89a750774e3daa80ee241e03e6","datavalue":{"value":"A proof of combinatorial complexity of the upper envelope of piecewise linear functions is given. The upper envelope of the system of functions is defined as a pointwise maximum of functions of this system. In the case of piecewise linear functions the envelope form a cell complex. The cardinality of all faces of this complex is called a combinatorial complexity of the envelope. It is shown that in the worst case the complexity of the envelope is \\(\\theta (n^ d\\alpha (n))\\), where \\(\\alpha\\) (n) is the inverse Ackermann's function and n is the number of linear parts of the function. The proof of this result is based on divide-and- conquer method.","type":"string"},"datatype":"string"},"type":"statement","id":"Q919829$395B0C9F-3AE6-4165-9616-FD3B309E0335","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q919829$2848DE9A-87DE-4AF7-B03D-F648F29C200B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q919829$295017AB-9499-4433-A9A2-23C1FE2F5FB7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q919829$C30E92A2-254A-4DB3-BA09-BA58335ACC13","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"86e788a8046e6f40998cb9d79f7af9045a3d62d2","datavalue":{"value":"4162269","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q919829$0CCE84FA-6726-4061-9E20-32ADEFF1187B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d7a39a1c143c36b9a508b6e0aad9580fb160eda5","datavalue":{"value":"combinatorial complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q919829$8B36E3C7-9808-41EC-AA90-817EAFFEEEB4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2f28fbafff413c9e12e452fcdf3c599ad000514f","datavalue":{"value":"piecewise linear functions","type":"string"},"datatype":"string"},"type":"statement","id":"Q919829$1DED1A58-65D0-4321-995E-7ACC825D41ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7dd06356e37adaf9e58284a5606844dc78b30811","datavalue":{"value":"envelope","type":"string"},"datatype":"string"},"type":"statement","id":"Q919829$BCEF7F58-CD82-492C-A92B-2B07D68B58B7","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"15fb7789dd0d1691819f44cebdb975938d5b89dc","datavalue":{"value":{"entity-type":"item","numeric-id":967347,"id":"Q967347"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q919829$1F760338-1EEB-4225-AF5A-79E2F394F02C","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":"Q919829$492C1665-F532-4B03-B502-61EEE99D2FC8","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"25b026e498c7466f890693e678f90760ff4b1c4e","datavalue":{"value":{"entity-type":"item","numeric-id":3772828,"id":"Q3772828"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q919829$10B8B8E7-EBE6-482B-A038-14AE42F0D7C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"261eaa97ac1f54a7ff7d57736e4928983bc92d96","datavalue":{"value":{"entity-type":"item","numeric-id":919830,"id":"Q919830"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q919829$3FDEA5BD-A516-4185-9A98-BB0C66A98875","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3f33e086a7a96a72aadab83cbb413d1e9523b8dd","datavalue":{"value":{"entity-type":"item","numeric-id":5557005,"id":"Q5557005"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q919829$E83B16E4-F24B-4FFB-A870-339628EACE07","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ff8fea9a5dba7c0c825c98a79aa7f9c13491987b","datavalue":{"value":{"entity-type":"item","numeric-id":5547252,"id":"Q5547252"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q919829$63224F44-1AD1-49D2-9D0C-ED0FE9B183E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c368a550cf5b4e92a6d4f0e58d9ca1eb20b223cd","datavalue":{"value":{"entity-type":"item","numeric-id":1097884,"id":"Q1097884"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q919829$CB6419C6-B2EC-4164-99A0-C7718E7AE597","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7268624479a5bc435fdb2e9183ce011e018dd2bd","datavalue":{"value":{"entity-type":"item","numeric-id":810525,"id":"Q810525"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q919829$BDC7D5D5-E06C-4EDF-8295-783E2BB28418","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9dd1104c3819dc61bbacb583d9a9ffa28e54bb09","datavalue":{"value":{"entity-type":"item","numeric-id":1098294,"id":"Q1098294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q919829$60252DA1-C63B-4815-820D-261C94001393","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"efcdf64824e3e249fa934a735c239c80cafba7eb","datavalue":{"value":{"entity-type":"item","numeric-id":810525,"id":"Q810525"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"88cb05023236728e10d9493f67702a8bc9c830d8","datavalue":{"value":{"amount":"+0.9208999872207642","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":"Q919829$9AF383B2-EE83-42C5-B4B4-F612898EC536","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"090f5802f2be4d20920ca9a37abda72c5d071bbf","datavalue":{"value":{"entity-type":"item","numeric-id":919830,"id":"Q919830"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"382ef7335a6ac5048ba8a6612ab840c937ecc5f3","datavalue":{"value":{"amount":"+0.8925637602806091","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":"Q919829$B97E5776-4527-4631-81F8-2D90A34F043B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2c9571bfab1e8b921d5e06b2b76e9df94811bd25","datavalue":{"value":{"entity-type":"item","numeric-id":1338960,"id":"Q1338960"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"366538d0fae91b6235883e65db1c8be28f29cf7c","datavalue":{"value":{"amount":"+0.8268762230873108","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":"Q919829$8AAE4C5C-BDD0-4FF7-9758-8105FC2348EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c14dd5e9af45a966cedc38993d0e8e86b411b010","datavalue":{"value":{"entity-type":"item","numeric-id":1199830,"id":"Q1199830"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3928621bd2eac490da1a6079017bf1cde90b9f8a","datavalue":{"value":{"amount":"+0.8267360329627991","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":"Q919829$72611393-E1CF-4DB3-90DC-13E98D49BA39","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d33eacc846d05877325dbf099e96c3bac6c821ff","datavalue":{"value":{"entity-type":"item","numeric-id":582095,"id":"Q582095"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b630f28cc3e53a21769520ce8e6da03a25eb5170","datavalue":{"value":{"amount":"+0.8247315883636475","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":"Q919829$78518B53-7255-493B-9111-95E7E9E260BF","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:919829","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:919829"}}}}}