World's most popular travel blog for travel bloggers.

# Help in geometrically understanding "Linear Decision Trees"

, ,
Problem Detail:

In the words of (http://www.cs.utah.edu/~suresh/5962/lectures/17.pdf, section 17.2), "Each $f(x)$ can be interpreted as deﬁning a hyperplane in $R^n$. Thus, tracing a path through the tree computes the intersection of the half-planes deﬁned by the nodes touched by the path."

I fail to visualize how path tracing is done? I would be glad to see it explained through the presentation of the path in a 2-dimensional space.

I do understand that $x_1,x_2,...,x_n$ is a point in the $R^n$ dimensional space. But I don't get how Figure 17.1 in (http://www.cs.utah.edu/~suresh/5962/lectures/17.pdf) helped in proving the lower bounds of Element Uniqueness as $\Omega(n\log n)$. I also don't get the implication of $\#F$ being connected components; why can't they simply be called solutions?

Unfortunately, reading online resources did not help me much understand the aforementioned concepts.

#### Answered By : Yuval Filmus

At each point in the linear decision tree, we branch according to whether $f(x) > 0$, $f(x) = 0$ or $f(x) < 0$, where $f$ is some linear functional. That means that the values of $x$ reaching some leaf are exactly those values satisfying some system of linear equations and inequalities \begin{align*} &f_1(x) = f_2(x) = \dots = f_a(x) = 0, \\ &g_1(x), g_2(x), \dots, g_b(x) > 0, \\ &h_1(x), h_2(x), \dots, h_c(x) < 0. \end{align*} Here $f_i,g_i,h_i$ are conditions encountered along the way. (In fact we can get rid of the $h$s, but this doesn't matter.) Each of these conditions — $f_i(x) = 0$, $g_j(x) > 0$ or $h_k(0) < 0$ — is convex, so their intersection is convex. This means that the set of all points getting to that leaf is convex, and in particular, either empty or connected.

In order to get a lower bound for element distinctness (for example), we show that the set $\{x : \text{all components of$x$are distinct}\}$ has many (in fact $n!$) connected components. If we take one vector each from all the connected components, then all these vectors must land at different leaves (why?), so there must be many leaves, hence the tree must be deep.