Suppose we have an arbitrary function $f : \mathbb{R}^2 \to \mathbb{R}$. For any subset $s \subseteq \mathbb{R}^2$, we can define $g\_f(s)$ as the integral\* of $f$ over the region $s$. Suppose further that we have access to an oracle that will tell us the value of $g\_f(s)$ for any $s$.


Now, restrict our attention to subsets of $s$ that are the convex hull of a given subset of points $\bar x\_c \subseteq \{x\_1, \ldots, x\_N \}$ with $x\_i \in \mathbb{R}^2$. Assuming calls to the oracle are O(1), what is the complexity (in terms of $N$) of finding $\bar x\_c^\* = \arg \max\_{\bar x\_c} g\_f(conv(\bar x\_c))$? Is there a known algorithm or reduction to a known problem?


EDIT: \*Previous statement that Scott answered said "average value" here.



Heaviest Convex Polygon
It should be polynomial (probably O(N^3)) in the number of input points using the dynamic programming technique in my paper with Overmars et al, "Finding minimum area k-gons", Disc. Comput. Geom. 7:45-58, 1992, [doi:10.1007/BF02187823](http://dx.doi.org/10.1007/BF02187823).


The idea is: for each three points p,q,r, let W[p,q,r] be the optimal convex polygon that has p as its bottommost point (smallest y-coordinate) and qr and rp as edges. We can calculate W[p,q,r] by looking at all choices of s for which psqr is convex and combining the (previously computed) value W[p,s,q] with the weight of triangle pqr.


As described above this takes time O(N^4) but I think that, for each pair of p and q one can examine the points s and r in the order of the slopes of the lines sq and sr, keeping track of the best s seen so far and using that choice of s for each r in this slope ordering, to reduce the time to O(N^3)


