Suppose one has a tree with each node weighted with a tuple (say, some fixed $2$ dimensions, for now) of integers. Now we query the tree with two vertices $x$ and $y$ and a range $[a,b]\times [c,d]$, and the query should return the number of nodes in the (unique) path from $x$ to $y$ such that their tuples fall within this rectangle $[a,b]\times [c,d]$. What would be a possible real-world scenario that would result in such a model?

For the 1d-case, one could use, say, Homory-Hu tree of minimum cuts to motivate such a problem. I am not sure how to motivate this theoretical question with a real-life problem, that is the question.

Suppose the path $x\sim y$ has vertices $u_1,u_2,\ldots,u_m$ with attached tuples (respectively) $(-1,2),(3,4),\ldots,(13,-17).$ Then if we query with $x,y$ and a rectangle $[-2,2]\times[2,3]$, then the first node, $u_1$ (among possibly others) would be counted, since its tuple $(-1,2) \in [-2,2]\times [2,3].$

  • 1
    $\begingroup$ You can ask this question for a lot of different theoretical problems. What makes this particular question special? $\endgroup$ – Yuval Filmus Apr 22 '19 at 13:47
  • 1
    $\begingroup$ What are you going to use this real-world scenario for? Why do you need to motivate your theoretical model? $\endgroup$ – Discrete lizard Apr 22 '19 at 14:31

Your Answer

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

Browse other questions tagged or ask your own question.