Heaviest Convex Polygon

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

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.

-

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

1
@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 2010 at 20:27
show 2 more comments

2 Answers

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 2010 at 19:57
If I could downvote my own reply, I would: Scott Carnahan's is much better. – David Eppstein Feb 2 2010 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 2010 at 20:11

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.

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.

-

2
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 2010 at 20:10
No problem. I'm glad the confusion got cleared up. – S. Carnahan♦ Feb 2 2010 at 20:24
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 14, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": false, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9475707411766052, "perplexity_flag": "middle"}