title: Finding all empty triangles
body: <p>I have a small set of <code>N</code> points in the plane, <code>N &lt; 50</code>.</p>
  
  <p>I want to enumerate all triples of points from the set that form a triangle containing no other point.</p>
  
  <p>Even though the obvious brute force solution could be viable for my tiny <code>N</code>, it has complexity <code>O(N^4)</code>.</p>
  
  <p>Do you know a way to decrease the time complexity, say to <code>O(N³)</code> or <code>O(N²)</code> that would keep the code simple ? No library allowed.</p>
  
  <hr>
  
  <p>Much to my surprise, the number of such triangles is pretty large. Take any point as a center and sort the other ones by increasing angle around it. This forms a star-shaped polygon, that gives <code>N-1</code> empty triangles, hence a total of <code>Ω(N²)</code>. It has been shown that this bound is tight [Planar Point Sets with a Small Number of Empty convex Polygons, I. Bárány and P. Valtr].</p>
  
  <p>In the case of points forming a convex polygon, all triangles are empty, hence <code>O(N³)</code>. Chances of a fast algorithm are getting low :(</p>