2
$\begingroup$

I'm trying to figure out the approximate number of areas the positive $n$-space will be divided into if we partition it as follows: we have $k$ linear functions $F_1$, $F_2$, ..., $F_k$ on $n$ variables (with positive "weights" for each variable) that return a real number, and we color every point in the $n$-space in one of $k$ colors depending on which $F_i$ returns the largest value (if there's a tie, select arbitrarily).

A naive upper bound would be to consider the $\binom{k}{2}$ hyperplanes by taking differences between pairs of functions then dividing the plane based on them, then the order of the values of the $n$ functions within each of the regions generated would be consistent. Since there are $\frac{k(k-1)}{2}$ hyperplanes, the number of regions is upper bounded at $O(n^{\frac{k(k-1)}{2}})$.

$\endgroup$
1
  • $\begingroup$ I do not understand. We partition onto $k$ parts, do we?$i$-th part is defined as $\{x:F_i(x)=\max_j F_j(x)\}.$ $\endgroup$ Nov 15, 2017 at 6:08

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.