Efficient algorithm to filter off points from a point cloud I have a master point cloud, which essentially just a list of points with {x,y} coordinates. 

The point cloud is HUGE ( like, it can contain more than 1 million points). The problem now is that I have another (sub)set of point clouds, and I need to check whether the points inside the second point clouds are the same with any of the points in the first point clouds, and then remove them from the list.

The characteristics of the second point cloud:


The second point cloud points are usually clustered in a corner of the first point cloud ( but not always).
None of the points from the second point cloud will lie outside of the first point cloud ( the first point cloud always contain every single point of the second point cloud)


The naive algorithm will be something like this:

   public static List&lt;Point&gt; FilterPoints(Lis&lt;Point&gt; master, List&lt;Point&gt; subset)
   {    
    var FilteredPoints = new List&lt;Point&gt;();    
    for(int i=0; i&lt; subset.Count; i++) 
    {
        var isContained = false;
        for(int j=0; j&lt; master.Count; j++)
        {
          if(subset[i].X==master[j].X &amp;&amp; subject[i].Y==master[j].Y)
          {
              isContained = true;
              break;
          }
        }
        if(!isContained)
        {
           FilteredPoints.Add( master[i]);
        }   
      } 
     return FilteredPoints; 
}


But is there anyway to improve over the above naive algorithm in terms of speed, given the known characteristics of the both point clouds?

PS: I've also asked about how to make use of C# language characteristics( if any) in order to improve the speed for the above algorithm at SO.
You should use a set data structure for your subset-list. This would allow querying if it contains a given point in constant time.

Your function, as python-like pseudocode:

def FilterPoints(master, subset):
    # take the list and convert it to a set ( O(|subset|)
    subset_set = set(subset)
    # iterate through master and and the points that are not in subset O(|master|)
    filtered_list = [p for p in master if p not in subset_set]
    return filtered_list


Some points:


If master is larger than subset, the algorithm will be $\mathcal O(|master|)$ 
The equivalent of set in C# should be HashSet