How to find largest triangle in convex hull aside from brute force search

Yes, you can do significantly better than brute-force.

By brute-force I assume you mean checking all triples of points, and picking the one with maximum area. This runs in O(n³) time, but it turns out that it is possible to do it in not just O(n²) but in O(n) time!

[Update: A paper published in 2017 showed by example that the O(n) solution doesn't work for a specific class of polygons. See this answer for more details. But the O(n²) algorithm is still correct.]

By first sorting the points / computing the convex hull (in O(n log n) time) if necessary, we can assume we have the convex polygon/hull with the points cyclically sorted in the order they appear in the polygon. Call the points 1, 2, 3, … , n. Let (variable) points A, B, and C, start as 1, 2, and 3 respectively (in the cyclic order). We will move A, B, C until ABC is the maximum-area triangle. (The idea is similar to the rotating calipers method, as used when computing the diameter (farthest pair).)

With A and B fixed, advance C (e.g. initially, with A=1, B=2, C is advanced through C=3, C=4, …) as long as the area of the triangle increases, i.e., as long as Area(A,B,C) ≤ Area(A,B,C+1). This point C will be the one that maximizes Area(ABC) for those fixed A and B. (In other words, the function Area(ABC) is unimodal as a function of C.)

Next, advance B (without changing A and C) if that increases the area. If so, again advance C as above. Then advance B again if possible, etc. This will give the maximum area triangle with A as one of the vertices.

(The part up to here should be easy to prove, and simply doing this separately for each A would give an O(n²) algorithm.)

Now advance A again, if it improves the area, and so on._{(The correctness of this part is more subtle: Dobkin and Snyder gave a proof in their paper, but a recent paper shows a counterexample. I have not understood it yet.)}

Although this has three "nested" loops, note that B and C always advance "forward", and they advance at most 2n times in total (similarly A advances at most n times), so the whole thing runs in O(n) time.

Code fragment, in Python (translation to C should be straightforward):

 # Assume points have been sorted already, as 0...(n-1)
 A = 0; B = 1; C = 2
 bA= A; bB= B; bC= C #The "best" triple of points
 while True: #loop A

   while True: #loop B
     while area(A, B, C) <= area(A, B, (C+1)%n): #loop C
       C = (C+1)%n
     if area(A, B, C) <= area(A, (B+1)%n, C): 
       B = (B+1)%n
       continue
     else:
       break

   if area(A, B, C) > area(bA, bB, bC):
     bA = A; bB = B; bC = C

   A = (A+1)%n
   if A==B: B = (B+1)%n
   if B==C: C = (C+1)%n
   if A==0: break

This algorithm is proved in Dobkin and Snyder, On a general method for maximizing and minimizing among certain geometric problems, FOCS 1979, and the code above is a direct translation of their ALGOL-60 code. Apologies for the while-if-break constructions; it ought to be possible to transform them into simpler while loops.

According to this paper, there is a class of convex polygons in which the algorithm cited by ShreevatsaR's answer fails. The paper also proposes a O(n log n) divide and conquer algorithm for solving the problem.

Apparently, the simpler O(n²) algorithm in which you move points B and C for all A is still valid.

answering your related question:

The circumcircle of the triangle is not necessarily the minimum bounding circle of the polygon. To see this, consider a very flat isosceles triangle, say with vertices at (0,0), (10,0) and (5,1). The minimum bounding circle has center (5,0) and radius 5, but this circle doesn't touch the vertex at (5,1), so it's not the circumcircle. (The circumcircle has center (5,-12) and radius 13)

edit:

Choosing the smaller of the circumcircle or the circle containing the antipodal points of the diameter of the polygon also doesn't suffice, because it is possible to construct polygons that have points outside the circumcircle of the maximal triangle. Consider the pentagon with vertices at:

(-5,  0)
(-4, -1)
( 5,  0)
( 4,  1)
(-4,  1)

The maximal triangle has vertices at (-4,-1), (5, 0), and (-4, 1). Its circumcircle does not include the point at (-5, 0).