Convexified threshold of a function - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T06:00:54Z http://mathoverflow.net/feeds/question/101589 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/101589/convexified-threshold-of-a-function Convexified threshold of a function Anton Sukhinov 2012-07-07T15:53:10Z 2012-07-08T08:40:26Z <p><strong>Upd.</strong> The question in a nutshell: <em>find convex set on plane which is «closest» to a given non-convex set</em>.</p> <p>It is given integrable function $0\leq f(x,y)\leq 1$ with bounded support: $f(x,y)=0$ when $x^2+y^2\geq R$. Needed to find function $t(x,y)$ which takes only two values («binary» function): <code>$t(x,y)\in\{0,1\}$</code> such as <code>$$\iint\limits_{x^2+y^2&lt;R}\left|f(x,y)-t(x,y)\right|dxdy\to\min.$$</code> We will call this task «threshold of a function». The solution is trivial: <code>$$t(x,y)=\left\{\begin{array}{cl}0&amp;\text{if }f(x,y)&lt;1/2;\\1&amp;\text{if }f(x,y)\geq1/2.\end{array}\right.$$</code> But what to do if I need to find threshold having convex support? I.e. I need to find a function <code>$c(x,y)\in\{0,1\}$</code> that have convex support and satisfies minimization criteria stated above among all binary functions with convex support. I can use any norm which will be convenient.</p> <p>I also interested in discrete analog of the problem: given set of points <code>$p_i=\{x_i,y_i\}\in\mathbb{R}^2$</code>, $i=1,...,N$, and values $0\leq v(p_i)\leq 1$. Find convex polygon $P$, such as <code>$$\sum_{p_i\in P}(1-v(p_i))+\sum_{p_i\notin P}v(p_i)\to\min.$$</code> I tried greedy algorithm to solve last problem: take convex hull of all points which have value $>1/2$ and then reduce convex hull point-by-point while target function decreases, but this fails for structures where 0-valued points are surrounded by 1-valued points.</p>