In the words of (http://www.cs.utah.edu/~suresh/5962/lectures/17.pdf, section 17.2), "Each $f(x)$ can be interpreted as defining a hyperplane in $R^n$. Thus, tracing a path through the tree computes the intersection of the half-planes defined 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.

Thank you in advance.

  • $\begingroup$ 1. What have you tried on your own? Have you tried working through an example of path tracing and tried drawing a picture of it yourself? 2. This seems like two separate questions tacked together. Your first question is "how is path tracing done?" and the second is "how does the figure help me prove lower bounds?" They would probably be better off as two separate questions; this site works best when you ask one question per question. $\endgroup$
    – D.W.
    Feb 27 '14 at 21:51

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.