given a set $A$ of $n$ points with integer coordinates in $\mathbb{R}^d$, and $k<d$ basis vectors of a subspace $K$ of $\mathbb{R}^d$, is there an efficient algorithm that returns all points from $A$ that lie on $K$? specifically, can I, given the answer for some subspace $K$, use it to find an answer for another subspace $K'$, the basis of which contains the basis of $K$ that I was given before, without looking at all of $A$?

  • $\begingroup$ I only know the very straightforward way of checking for each point if it belongs in that space or not (via Gaussian elimination for example). I thought (maybe wrongly so) that the second question is related to the first in a sense that an answer to it contains the answer for the first (although perhaps I should have then formulated it otherwise). an explanation is definitely due to the second question: given an output for some $K$, a basis $b$ for $K$ and basis $b'$ for some $K'$ that contains $b$, can I solve the said problem in less than $O(n)$ time? $\endgroup$ – Ron Tubman Sep 22 '17 at 10:25
  • $\begingroup$ As of the problem being research-level or not, I couldn't figure where else I should ask, so I tried here. Thanks for the comment! $\endgroup$ – Ron Tubman Sep 22 '17 at 10:31
  • $\begingroup$ I'm focusing on such a case where $k<=n$ and $n>>d$. Thanks for the help! $\endgroup$ – Ron Tubman Sep 23 '17 at 6:49

One straightforward approach is to first compute a $d \times k-d$ matrix $M$ such that $Mx=0$ iff $x \in K$. Then you can determine which points from $A$ lie on $K$ by computing $Mx$ for each $x \in A$. The running time for that will be $O(d^3 + k(d-k)n)$ or so, i.e., $O(d^3 + d^2 n)$. Since the input has size $dn$, any solution has to take $\Omega(dn)$ time. Thus this solution is at most a $d$ times factor slower than the best possible.

You mention in the comments that you are interested in the case $k,d \ll n$. This might suggest counting the running time as a function of $n$, i.e., focus primarily on the dependence on $n$, and largely ignore the dependence on $k,d$. As a function of $n$ (treating $k,d$ as constants), the solution above runs in $O(n)$ time.


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.