# given a set of $n$ points in $d$-dimensional space and the basis vectors of some subspace, how to find all the points on that space?

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$?

• 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? – Ron Tubman Sep 22 '17 at 10:25
• 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! – Ron Tubman Sep 22 '17 at 10:31
• I'm focusing on such a case where $k<=n$ and $n>>d$. Thanks for the help! – 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.