5
$\begingroup$

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.

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ g_f doesn't always exist without some kind of assumption on f. For example, is f continuous? $\endgroup$
    – Qiaochu Yuan
    Feb 2, 2010 at 18:26
  • $\begingroup$ 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? $\endgroup$
    – user2498
    Feb 2, 2010 at 18:28
  • $\begingroup$ We can assume $f$ is bounded. Is that good enough? $\endgroup$
    – Andrew
    Feb 2, 2010 at 18:30
  • $\begingroup$ I'm only interested in complexity in terms of the number of points N. $\endgroup$
    – Andrew
    Feb 2, 2010 at 18:31
  • 1
    $\begingroup$ @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.) $\endgroup$
    – Qiaochu Yuan
    Feb 2, 2010 at 20:27

2 Answers 2

Reset to default
5
$\begingroup$

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)

Improve this answer
$\endgroup$
3
  • $\begingroup$ Excellent--this makes sense and I will think about it further. Thank you! $\endgroup$
    – Andrew
    Feb 2, 2010 at 19:57
  • $\begingroup$ If I could downvote my own reply, I would: Scott Carnahan's is much better. $\endgroup$
    – David Eppstein
    Feb 2, 2010 at 20:07
  • $\begingroup$ I responded to his comment and upvoted his answer. Somehow you read what I intended to write even though I completely mis-stated it. $\endgroup$
    – Andrew
    Feb 2, 2010 at 20:11
6
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ 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. $\endgroup$
    – Andrew
    Feb 2, 2010 at 20:10
  • $\begingroup$ No problem. I'm glad the confusion got cleared up. $\endgroup$
    – S. Carnahan ♦
    Feb 2, 2010 at 20:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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