Convexified threshold of a function

2012-07-07T15:53:10Z

Upd. The question in a nutshell: find convex set on plane which is «closest» to a given non-convex set.

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): $t(x,y)\in\{0,1\}$ such as $$\iint\limits_{x^2+y^2<R}\left|f(x,y)-t(x,y)\right|dxdy\to\min.$$ We will call this task «threshold of a function». The solution is trivial: $$t(x,y)=\left\{\begin{array}{cl}0&\text{if }f(x,y)<1/2;\\1&\text{if }f(x,y)\geq1/2.\end{array}\right.$$ But what to do if I need to find threshold having convex support? I.e. I need to find a function $c(x,y)\in\{0,1\}$ 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.

I also interested in discrete analog of the problem: given set of points $p_i=\{x_i,y_i\}\in\mathbb{R}^2$ , $i=1,...,N$, and values $0\leq v(p_i)\leq 1$. Find convex polygon $P$, such as $$\sum_{p_i\in P}(1-v(p_i))+\sum_{p_i\notin P}v(p_i)\to\min.$$ 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.

Convexified threshold of a function - MathOverflow

Convexified threshold of a function