<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2017-09-24T00:14:45.087Z
2017-09-24T00:14:45.087Z
D.W.
<p>given a set $A$ of $n$ points with integer coordinates in $\mathbb{R}^d$, and $k&lt;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$?</p>

CC BY-SA 3.0
2017-09-22T10:25:22.790Z
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
CC BY-SA 3.0
2017-09-22T10:31:41.390Z
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
CC BY-SA 3.0
2017-09-23T06:49:47.437Z
I'm focusing on such a case where $k<=n$ and $n>>d$. Thanks for the help!
Ron  Tubman
<ds.algorithms><linear-algebra><computational-geometry><data-sets>
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?
Ron  Tubman
# 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?

(Asked by: username_0 on 2017-09-21)

given a set $A$ of $n$ points with integer coordinates in $\mathbb{R}^d$, and $k

**Tags:** ds.algorithms, linear-algebra, computational-geometry, data-sets

> **Comments:**
> **username_0**: 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?  
> **username_0**: 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!  
> **username_0**: I'm focusing on such a case where $k<=n$ and $n>>d$. Thanks for the help!  

---

## 1 answers

### Answer by username_1 on 2017-09-24. Score: 1

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.


---

