Appropriate partition region in a decision tree? I have the following partition region for a decision tree, but I do not think it is a valid region: 
$R=(\vec{X}=(X_1, X_2, ..., X_p)^T\in \mathbb{R}^p: X_1X_2 \geq 3)$
I feel that this is not a valid partition region because regions should always be disjoint from one another as the $p$ predictors are being divided amongst the $J$ regions. Can someone help me understand the reasoning behind this?
 A: From The Elements of Statistical Learning section 9.2:

Tree-based methods partition the feature space into a set of
  rectangles, and then fit a simple model (like a constant) in each one.

So, if I'm understanding your question correctly, we need to decide if your region $R$ can be represented as a union of a finite number of disjoint rectangles, where a rectangle in $\mathbb R^p$ is a set of the form $[a_1, b_1] \times \dots \times [a_p, b_p]$.
We can answer this by building a geometric picture of $R$. Think about the function $f(x,y) = xy$. $f$ is a hyperbolic paraboloid and looks like this:

Contours of $f$, like $\{(x, y)  :f(x,y) = 3\}$, are intersections of this function with a plane parallel to the $xy$ axes and result in standard hyperbolas. This means that we can picture the region $\{f \geq 3\}$ as starting with the hyperbola corresponding to the level set $f = 3$ and then sliding this plane upwards to fill it in solidy. The result looks like this:

Now let's consider $\{(x, y, z) : xy \geq 3\}$. If we look at the projection onto the $xy$ plane, we'll again see the filled-in hyperbola as above. And $z$ is unconstrained and doesn't interact with $x$ and $y$, so for every $z \in \mathbb R$ we get the exact same slice, so the result is like the infinite prism made by translating $\{f \geq 3\}$ along all of the $z$ axis.
I can't picture this in higher dimensions, but the principle is the same. We get $p-2$ dimensions of unconstrained space and the projection onto the $X_1$-$X_2$ plane is always this filled in hyperbola. This means that if we let $H = \{(x, y) : xy \geq 3\} \subset \mathbb R^2$ then we can write
$$
R = H \times \mathbb R^{p-2}.
$$
This shows that representing $R$ in terms of $p$-dimensional boxes comes down to representing $H$ in terms of $2$-dimensional boxes. And clearly we can't do that, as each box corresponds to axis-parallel splits and yet there's curvature that is not axis-parallel.

As @hxd1011 points out in the comments, we can fix this if we allow feature transformations. As stated, this question asks if a decision tree can exactly capture an interaction between two continuous features, which it cannot. But if all we want is the interaction then we can replace $X_1$ and $X_2$ in our dataset with $X_1 X_2$ (so our modified dataset now lives in $\mathbb R^{p-1}$, not $\mathbb R^p$) and now we are in fact considering an axis-parallel split given by the box $[3, \infty) \times \mathbb R^{p-2}$. So this is axis parallel in our transformed space but not in the original space.
