<p>For a directed tree, it is possible to find an embeeding in a n-dimensional space, where n is the maximum branching factor of the tree. This approach could be also generalized for (rooted) DAGs.</p>
<p>More to come in the forthcoming paper: <a href="https://www.researchgate.net/publication/342902961_Hierarchical_Embedding_for_DAG_Reachability_Queries" rel="nofollow noreferrer">https://www.researchgate.net/publication/342902961_Hierarchical_Embedding_for_DAG_Reachability_Queries</a></p>

CC BY-SA 4.0
2020-07-19T00:01:17.583Z
2020-07-19T00:01:17.583Z
jackb
<p>This is not possible if the dimension <span class="math-container">$m$</span> is fixed. Consider a complete <span class="math-container">$b$</span>-ary tree, in which all edges are oriented from the root <span class="math-container">$r$</span>. Then all vertices lie in a ball of radius <span class="math-container">$h$</span> around <span class="math-container">$v_r$</span>. On the other hand, the distance between every two leaves is greater than <span class="math-container">$h$</span>. Since there are <span class="math-container">$N = b^h$</span> leaves, we get that </p>

<blockquote>
  <p>there are <span class="math-container">$N$</span> points in a ball of radius <span class="math-container">$h$</span> such that all the pairwise distances between the points are greater than <span class="math-container">$h$</span></p>
</blockquote>

<p>We must have that <span class="math-container">$m = \Omega(\log N) = \Omega(h \log b)$</span>.</p>

CC BY-SA 4.0
2019-06-05T16:24:54.053Z
Thanks. I'll edit my question. What if m=hb, so to meet the omega requirement?
jackb
CC BY-SA 4.0
2019-06-05T16:21:36.397Z
2019-06-05T16:21:36.397Z
Yury
<p>Given a (directed) n-tree <span class="math-container">$T=(N,E,r)$</span> rooted in <span class="math-container">$r\in N$</span>, I want to represent each node <span class="math-container">$n\in N$</span> at most as a <span class="math-container">$m$</span>-dimensional vector <span class="math-container">$v_n\in \mathbb{R}^m$</span> (From the current Yuri's reply, m cannot be <span class="math-container">$b$</span>). In particular, given <span class="math-container">$h$</span> the height of the tree (that is, the maximum path length starting from <span class="math-container">$r$</span>), I want to guarantee that <span class="math-container">$\forall a,b\in N. \|v_a-b_b\|_2\leq h$</span> if and only if there exists a directed path <span class="math-container">$\pi(a,b)$</span> or <span class="math-container">$\pi(b,a)$</span> in <span class="math-container">$T$</span>.</p>

<p><strong>Example</strong>, given the following tree rooted in <span class="math-container">$1$</span>, <span class="math-container">$(\{1,2,3,4\},\;\{(1,2), (1,3),(3,4)\},1)$</span>, I would instantiate the distance constraints as follows:</p>

<ul>
<li><span class="math-container">$\forall (a,b)\in E\cup \{(b,a)|(a,b)\in E\}. \|v_a-v_b\|_2\leq 1$</span></li>
<li><span class="math-container">$\|v_1-v_4\|_2\leq 2$</span> by transitive closure</li>
<li><span class="math-container">$\forall (a,b)\in V^2\backslash (E\cup \{(b,a)|(a,b)\in E\}. 3\leq \|v_a-v_b\|_2\leq 4$</span></li>
</ul>

<p>I was thinking to reduce this problem into the Distance Geometry Problem, and to use the former distances to feed known solvers like DGSOL or MD-Jeep: while the first commits non-negligible errors, MD-Jeep returns some errors during the computation of the torsion angle, and therefore cannot provide a viable solution. Is this a problem of the Distance Geometry Problem itself, or are there other implementations that would not suffer from the same problem? Alternatively, is it possible to express this problem using mathematical programming, i.e. using one of the already existing libraries?</p>

<optimization><computational-geometry>
Embedding a n-tree into a b-dimensional space
jackb
# Embedding a n-tree into a b-dimensional space

(Asked by: username_0 on 2019-06-04)

Given a (directed) n-tree $T=(N,E,r)$ rooted in $r\in N$, I want to represent each node $n\in N$ at most as a $m$-dimensional vector $v\_n\in \mathbb{R}^m$ (From the current Yuri's reply, m cannot be $b$). In particular, given $h$ the height of the tree (that is, the maximum path length starting from $r$), I want to guarantee that $\forall a,b\in N. \|v\_a-b\_b\|\_2\leq h$ if and only if there exists a directed path $\pi(a,b)$ or $\pi(b,a)$ in $T$.

**Example**, given the following tree rooted in $1$, $(\{1,2,3,4\},\;\{(1,2), (1,3),(3,4)\},1)$, I would instantiate the distance constraints as follows:

* $\forall (a,b)\in E\cup \{(b,a)|(a,b)\in E\}. \|v\_a-v\_b\|\_2\leq 1$
* $\|v\_1-v\_4\|\_2\leq 2$ by transitive closure
* $\forall (a,b)\in V^2\backslash (E\cup \{(b,a)|(a,b)\in E\}. 3\leq \|v\_a-v\_b\|\_2\leq 4$

I was thinking to reduce this problem into the Distance Geometry Problem, and to use the former distances to feed known solvers like DGSOL or MD-Jeep: while the first commits non-negligible errors, MD-Jeep returns some errors during the computation of the torsion angle, and therefore cannot provide a viable solution. Is this a problem of the Distance Geometry Problem itself, or are there other implementations that would not suffer from the same problem? Alternatively, is it possible to express this problem using mathematical programming, i.e. using one of the already existing libraries?

**Tags:** optimization, computational-geometry


---

## 2 answers

### Answer by username_0 on 2020-07-19. Score: 0 | Accepted answer

For a directed tree, it is possible to find an embeeding in a n-dimensional space, where n is the maximum branching factor of the tree. This approach could be also generalized for (rooted) DAGs.

More to come in the forthcoming paper: <https://www.researchgate.net/publication/342902961_Hierarchical_Embedding_for_DAG_Reachability_Queries>


---

### Answer by username_1 on 2019-06-05. Score: 1

This is not possible if the dimension $m$ is fixed. Consider a complete $b$-ary tree, in which all edges are oriented from the root $r$. Then all vertices lie in a ball of radius $h$ around $v\_r$. On the other hand, the distance between every two leaves is greater than $h$. Since there are $N = b^h$ leaves, we get that

> there are $N$ points in a ball of radius $h$ such that all the pairwise distances between the points are greater than $h$

We must have that $m = \Omega(\log N) = \Omega(h \log b)$.

> **Comments:**
> **username_0**: Thanks. I'll edit my question. What if m=hb, so to meet the omega requirement?  

---

