3
$\begingroup$

Verbose Motivation for this Question

Inspired by this paper about how the problem of counting unlabelled subtrees that are unique up to isomorphism is #P-complete, I was thinking about the problem for the specific case of caterpillar graphs. (a caterpillar graph, $C$, will become a path graph, $P(C)$, by removing all their leaves) This lead me to an interesting subproblem, where, given an array $[l_0,l_1 \dots l_d]$ you need to compute:

$$ \sum_{i=0}^d \int \bigcup_{k=0}^{d-i} \prod_{j=k}^{k+i} [0,l_j]$$

Here, we are taking a Lebesgue unit measure of a union of $(i+1)$-dimensional intervals. (for each cartesian product, the length of 1st dimension is $[0,l_k]$, and the $m$th dimension is $[0,l_{j+m}]$) This monstrous equation arises due to the partial-order of possible sub-trees which include exactly $(i+1)$ vertices of $P(C)$. (in the actual problem, it's a little complicated, because you have to account for over-counting due to symmetry that occurs from reversing the order of your array, but for now I'll just concern myself with the cleaner subproblem)

My actual questions

I'm curious about computing the Lebesgue unit measure of the union of $n$ $i$-dimensional intervals which are each defined by a list of $i$ 2-tuples which are represent a cartesian product along orthogonal axes.

  1. What's the complexity of measuring the union of $n$ $i$-dimensional intervals? (I found that this is Klee's measure problem, we specifically have $O(n^{d/2})$ for dimensions $d \geq 3$, and $O(nlog(n))$ for $d =1,2$)
  2. Are there significant improvements in the case were intervals have some obvious partial-order? (ex: each interval is a subset of $[0, +\infty]^i$, and have a corner at $[0]^i$)
  3. Similarly, are there note-worthy improvements if we restrict ourselves to intervals whose corners all belong to $\mathbb{Z}^i$?

Upon further consideration, I feel like the answer to this question might be quite useful for my second question. However, I am still unclear exactly what's the best way to calculate measure once we've identified the relevant intervals, and if the $O(nlog(n))$ sorting generalizes to higher dimensions.

$\endgroup$

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.