1
$\begingroup$

So I saw this question posed on math.se for $d=3$. Suppose we are given a finite set $X \subset {\mathbb Z}^d$ of $n$ points. The goal is to find a hyper box of integer points $ B = [k_{1,1},k_{1,2}] \times [k_{2,1},k_{2,2}] \times \ldots \times [k_{d,1},k_{d,2}] $ so that the Jaccard distance $d(X,B)$ is minimized. The Jaccard distance is $d(X,B) = 1 - |X \cap B| / |X \cup B|$.

So obviously we can just restrict the range of the box to be defined by coordinates of points in $X$ in the appropriate dimension. So there are "only" $O(n^{2d})$ boxes to check. Furthermore, the Jaccard distance can be computed in constant time if $|X \cap B|$ is known, because $|X|$ is known and $|B|$ is easily calculated.

So, since the original problem was formulated for $d=3$, it occurred to me that the computation of $|X \cap B|$ could be reduced to $O(\log ^{d-1} n)$ time (instead of naïve $O(n)$ time) using a modified layered range tree that returns counts of points that satisfy a given range query.

However, I could not think of any way to avoid testing all possible hyper boxes, especially if $X$ is dense. Thus my speed-up is very minor compared to the overwhelming complexity of checking all boxes. Is there a way to speed up to better than $O(n^{2d} \log^{d-1} n)$ time, and if nothing else, at least in certain cases, like if $X$ is dense or sparse?

$\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.