Heaviest Convex Polygon - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-18T23:27:39Z http://mathoverflow.net/feeds/question/13844 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/13844/heaviest-convex-polygon Heaviest Convex Polygon Andrew 2010-02-02T18:18:52Z 2010-02-22T00:31:38Z <p>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$.</p> <p>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?</p> <p>EDIT: *Previous statement that Scott answered said "average value" here.</p> http://mathoverflow.net/questions/13844/heaviest-convex-polygon/13855#13855 Answer by David Eppstein for Heaviest Convex Polygon David Eppstein 2010-02-02T19:37:22Z 2010-02-02T19:37:22Z <p>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, <a href="http://dx.doi.org/10.1007/BF02187823" rel="nofollow">doi:10.1007/BF02187823</a>.</p> <p>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.</p> <p>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)</p> http://mathoverflow.net/questions/13844/heaviest-convex-polygon/13863#13863 Answer by S. Carnahan for Heaviest Convex Polygon S. Carnahan 2010-02-02T19:57:29Z 2010-02-02T19:57:29Z <p>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.</p>