# Heaviest Convex Polygon

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.

-
g_f doesn't always exist without some kind of assumption on f. For example, is f continuous? –  Qiaochu Yuan Feb 2 '10 at 18:26
If you're asking about computational complexity, then you'll need to be more specific about the inputs. How will f be described as an input? –  user2498 Feb 2 '10 at 18:28
We can assume $f$ is bounded. Is that good enough? –  Andrew Feb 2 '10 at 18:30
I'm only interested in complexity in terms of the number of points N. –  Andrew Feb 2 '10 at 18:31
@Konrad, there are no computability issues if one assumes that the oracle g works. g, restricted to subsets of the given set of points, only knows a finite amount of data - more precisely, the integral of f over the regions cut out by all lines among the given points. (Also, the answer I gave below - which I have deleted - was in response to the original formulation of the question.) –  Qiaochu Yuan Feb 2 '10 at 20:27

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.

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)

-
Excellent--this makes sense and I will think about it further. Thank you! –  Andrew Feb 2 '10 at 19:57
If I could downvote my own reply, I would: Scott Carnahan's is much better. –  David Eppstein Feb 2 '10 at 20:07
I responded to his comment and upvoted his answer. Somehow you read what I intended to write even though I completely mis-stated it. –  Andrew Feb 2 '10 at 20:11
Oh oh, of course. I apologize, I want $g$ to be the integral, not average value. Somehow David knew what I was talking about even though I wrote it completely wrong. I updated the question and profusely apologize for the mis-statement of the problem. –  Andrew Feb 2 '10 at 20:10