title: Skyline of 2D points-Divide and conquer algorithm
body: <p>I'm working on a project where I have to find the skyline of the points that are not dominated by any other point in the set. A point A(x1,y1) dominates point B(x2,y2) if x1&lt;=x2 &amp;&amp; y1&lt;=y2. <a href="https://i.stack.imgur.com/sxZqq.jpg" rel="nofollow noreferrer">Here's an example</a></p>
  
  <p>This is my code:</p>
  
  <pre><code>public static ArrayList&lt;Point&gt; findSkyline(ArrayList&lt;Point&gt; pointsList){
      if (pointsList.size()&lt;=1){
          return pointsList;
      }
  
      ArrayList&lt;Point&gt; leftSkylinePoints=new ArrayList&lt;&gt;();
      ArrayList&lt;Point&gt; rightSkylinePoints=new ArrayList&lt;&gt;();
      ArrayList&lt;Point&gt; leftPoints=new ArrayList&lt;&gt;();
      ArrayList&lt;Point&gt; rightPoints=new ArrayList&lt;&gt;();
  
      for (int i=0;i&lt;pointsList.size()/2;i++){
          leftPoints.add(pointsList.get(i));
      }
      for (int i=pointsList.size()/2;i&lt;pointsList.size();i++){
          rightPoints.add(pointsList.get(i));
      }
  
      leftSkylinePoints=findSkyline(leftPoints);
      rightSkylinePoints=findSkyline(rightPoints);
  
      int minY=1001;
      for (int i=0;i&lt;leftSkylinePoints.size();i++){
          if (leftSkylinePoints.get(i).y&lt;minY){
              minY=leftSkylinePoints.get(i).y;
          }
      }
      for (int i=0;i&lt;rightSkylinePoints.size();i++){
          if (rightSkylinePoints.get(i).y&gt;=minY){
              rightSkylinePoints.remove(i);
          }
      }
  
      System.out.println("MINY: "+minY);
  
      System.out.print("Left: ");
      for (int i=0;i&lt;leftSkylinePoints.size();i++){
          System.out.print("("+leftSkylinePoints.get(i).x+","+leftSkylinePoints.get(i).y+") ");
      }
      System.out.println();
      System.out.print("Right: ");
      for (int i=0;i&lt;rightSkylinePoints.size();i++){
          System.out.print("("+rightSkylinePoints.get(i).x+","+rightSkylinePoints.get(i).y+") ");
      }
      System.out.println();
      System.out.println();
  
  
      leftSkylinePoints.addAll(rightSkylinePoints);
      return leftSkylinePoints;
  }
  </code></pre>
  
  <p><a href="https://i.stack.imgur.com/yBgDl.png" rel="nofollow noreferrer">These are the results.</a></p>
  
  <p>As you can see point (6,2) appears to be in the skyline but it shouldn't be because it should have been deleted in the second for loop. Does anyone know why this is happening? Thanks!</p>
  
  <p>*For more points I get a lot more that shouldn't be there but for now I want to know about this situation.</p>
  
  <p>**Points are sorted based on their x values (ascending)</p>