MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

4 deleted 8 characters in body

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(CONVEX-HULL(\bar 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.

3 fixed a big mistake mixing up average and integral; added 77 characters in body

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) = \mathbb{E}(f \mid s)$ g_f(s)$as the average value 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(CONVEX-HULL(\bar x_c))$? Is there a known algorithm or reduction to a known problem? EDIT: *Previous statement that Scott answered said "average value" here. 2 clarified (hopefully) question about computational complexity 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) = \mathbb{E}(f \mid s)$as the average value 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$. What 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(CONVEX-HULL(\bar x_c))\$? Is there a known algorithm or reduction to a known problem?

1