. . "Simplifying inclusion-exclusion formulas" . "10.1007/978-88-7642-475-5_88" . "Scuola Normale Superiore" . "Goaoc, Xavier" . "Tancer, Martin" . . . "11320" . "4"^^ . "P(GEGIG/11/E023), S" . "Simplifying inclusion-exclusion formulas"@en . . "Simplifying inclusion-exclusion formulas"@en . . "105136" . "RIV/00216208:11320/13:10190922" . "Pisa" . "Venn diagram; inclusion - exclusion formula"@en . "Pisa" . "The Seventh European Conference on Combinatorics, Graph Theory and Applications; EuroComb 2013" . . "Safernov\u00E1, Zuzana" . . "978-88-7642-474-8" . . "5"^^ . "http://link.springer.com/chapter/10.1007/978-88-7642-475-5_88" . . . . "Let F = (F 1, F 2, ..., F n) be a family of n sets on a ground set S, such as a family of balls in R d. For every finite measure \u03BC on S, such that the sets of F are measurable, the classical inclusion-exclusion formula asserts that \u03BC (F 1 UNION F 2 UNION ...UNION F n) = N-ARY SUMMATIONI:oNOT EQUAL TOSUBSET OF OR EQUAL TO \u00A0[n] (MINUS SIGN 1)|I|+1\u03BC(INTERSECTIONi ELEMENT OFIF i); that is, the measure of the union is expressed using measures of various intersections. The number of terms in this formula is exponential in n, and a significant amount of research, originating in applied areas, has been devoted to constructing simpler formulas for particular families F. We provide an upper bound valid for an arbitrary F: we show that every system F of n sets with m nonempty fields in the Venn diagram admits an inclusion-exclusion formula with m O (log2 n) terms and with +-1 coefficients, and that such a formula can be computed in m O (log2 n) expected time." . . . "Simplifying inclusion-exclusion formulas" . . . "Matou\u0161ek, Ji\u0159\u00ED" . . "RIV/00216208:11320/13:10190922!RIV14-GA0-11320___" . "Let F = (F 1, F 2, ..., F n) be a family of n sets on a ground set S, such as a family of balls in R d. For every finite measure \u03BC on S, such that the sets of F are measurable, the classical inclusion-exclusion formula asserts that \u03BC (F 1 UNION F 2 UNION ...UNION F n) = N-ARY SUMMATIONI:oNOT EQUAL TOSUBSET OF OR EQUAL TO \u00A0[n] (MINUS SIGN 1)|I|+1\u03BC(INTERSECTIONi ELEMENT OFIF i); that is, the measure of the union is expressed using measures of various intersections. The number of terms in this formula is exponential in n, and a significant amount of research, originating in applied areas, has been devoted to constructing simpler formulas for particular families F. We provide an upper bound valid for an arbitrary F: we show that every system F of n sets with m nonempty fields in the Venn diagram admits an inclusion-exclusion formula with m O (log2 n) terms and with +-1 coefficients, and that such a formula can be computed in m O (log2 n) expected time."@en . "[73AC8304DEA9]" . "7"^^ . . "2013-09-09+02:00"^^ . "Pat\u00E1k, Pavel" . . .