Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
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
show 2 more comments

2 Answers

up vote 5 down vote accepted

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)

share|improve this answer
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
add comment

I'm assuming the N points are fixed ahead of time. In that case, it seems to me that you can just use the oracle on each triple of points, since any convex polygon with more than three sides will have average at most the maximum of the averages over triangles in any triangulation. This gives you O(N^3) at worst.

share|improve this answer
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
No problem. I'm glad the confusion got cleared up. –  S. Carnahan Feb 2 '10 at 20:24
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.