Can every (convex) polygon be described by a single inequality (involving absolute values)?

Question

For example,

$$ |x| + |2x + y| + |x + 2y| + |y| + |x+y| < 4 $$ describes an octagon. I'm wondering whether an equation of this form always exist for any convex polygon, and if so, whether there is a systematic way to obtain it from a set of inequalities whose intersections form the polygon.

For example, this describes a square:

$$ y < x + 1 \cap y > x - 1 \cap y < -x + 1 \cap y > -x -1 $$

but this is the same as $$ |x| + |y| < 1 $$

Is there a general procedure to get from the intersection form to a single equation?

Answer 1

The sum $|t|+t$ is null on one side and positive on the other, so the inside of any convex polygon can be defined as

$$\sum_kw_k\left(|a_kx+b_ky+c_k|+a_kx+b_ky+c_k\right)\le0,$$ where the $w_k$ are positive weights and $(a_k,b_k,c_k)$ are the coefficients of the equations of the edges.

In addition, for a closed polygon you can always ensure that $$\sum_k w_ka_k=\sum_k w_kb_k=0.$$

For example, take the triangle through $(0,0), (1, 0), (0, 1)$, i.e sides $-x=0$, $-y=0$ and $x+y-1=0$ (LHS negative inside). Using equal weights,

$$|-x|+|-y|+|x+y-1|\le 1.$$

Answer 2

Given any $3$ non-collinear points $A,B,C \in \mathbb{R}^2$. Let $\Delta$ be the triangle with $A,B,C$ as vertices. Let $h_A, h_B, h_C$ be the heights of $\Delta$ for corresponding vertices. It is known that for any point $P$ on the plane, there exists a unique pair of real numbers $\alpha,\beta$ such that

$$\vec{P} - \vec{C} = \alpha(\vec{A}-\vec{C}) + \beta(\vec{B} - \vec{C}) \quad\iff\quad \vec{P} = \alpha \vec{A} + \beta \vec{B} + (1-\alpha-\beta)\vec{C}$$ Let $\gamma = 1 - \alpha - \beta$, the triplet $(\alpha,\beta,\gamma)$ is known as the baricentric coordinates of point $P$ with respect to $\Delta$. In terms of $(\alpha,\beta,\gamma)$, $P$ lies inside or on $\Delta$ when and only when $\alpha, \beta, \gamma$ are all non-negative.

For any line $\ell \subset \mathbb{R^2}$, let $d(P,\ell)$ be the distance between the point $P$ and line $\ell$.

$$d(P,\ell) \stackrel{def}{=} \inf\big\{\; |\vec{P} - \vec{Q}| : Q \in \ell\; \big\}$$

Associate $\Delta$ with following function

$$f_{\Delta}(P) = \frac{1}{h_A} d(P,\overline{BC}) + \frac{1}{h_B} d(P,\overline{CA}) + \frac{1}{h_C}d(P,\overline{AB}) - 1$$

Notice $$ |\alpha_P| h_A = d( P, \overline{BC} ),\quad |\beta_P| h_B = d( P, \overline{CA} ),\quad\text{ and } |\gamma_P | h_C = d( P, \overline{AB} ) $$ We have $$f_\Delta(P) = |\alpha_P| + |\beta_P| + |\gamma_P| - 1 \ge \alpha_P + \beta_P + \gamma_P - 1 = 0$$ Furthermore, the inequality is strict unless $\alpha_P, \beta_P, \gamma_P \ge 0$ which in turn is equivalent to the condition $P \in \Delta$.

What this means is any non-degenerate triangle $\Delta$ can be represented as the level set for an absolute value equation $f_\Delta(P) = 0$.

Given any convex $n$-gon $X$, we know it can be represented as the intersection of $n$ half-planes $H_1, H_2, \ldots, H_n$ whose supporting lines containing the corresponding side of $X$. $$X = \bigcap_{i=1}^n H_i$$ For each $H_i$, find a triangle $\Delta_i$ so that one of its side is lying on the corresponding support line and large enough to contain $X$. In this way, we can rewrite $X$ as

$$X = \bigcap_{i=1}^n \Delta_i$$

Let $f_X(P) = \sum\limits_{i=1}^n f_{\Delta_i}(P)$. Since $f_{\Delta_i}(\cdot)$ are non-negative, so does $f_X(\cdot)$. It is easy to see

$$f_X(P) = 0 \iff f_{\Delta_i}(P) = 0, \forall i \iff P \in \Delta_i, \forall i \iff P \in \bigcap_{i=1}^n \Delta_i = X$$

From this, we can conclude every convex $n$-gon $X$ can be written the level set of an absolute value equation $f_X(P) = 0$ which contains at most $3n$ terms of absolute values of the from $|ax + by + c|$ plus one extra constant term.

Finally, as mentioned in the comment, the best reference of this topic is probably following book:

• 绝对值方程——折边与组合图形的解析研究
  (Absolute Value Equation - Analytical Research on Folding and Composite Figure)
  author: 林世保, 楊世明.
  publisher: 哈爾濱工業大學出版社.
  ISBN, 9787560335124

and the two authors dedicate the whole book to study how to represent geometric figures using "absolute value equations".

Update

Thinking more about this, there is a much simpler solution!

Given any convex $n$-gon $X$ with vertices $(x_1,y_2)$, $(x_2, y_2), \ldots, (x_n,y_n)$, ordered counter-clockwisely around $X$ as a region. Let $\mathcal{A}$ be the area of $X$ and $(x_0,y_0) = (x_n,y_n)$.

For every point $(x,y) \in \mathbb{R}^2$, define the function

$$A_k(x,y) \stackrel{def}{=} \frac12\left|\begin{matrix} 1 & x & y\\ 1 & x_{k-1} & y_{k-1} \\ 1 & x_k & y_k\end{matrix}\right|$$

It is clear

1. $|A_k(x,y)|$ is the area of the triangle with vertices $(x,y), (x_{k-1},y_{k-1}), (x_k,y_k)$.
2. $\sum\limits_{k=1}^n A_k(x,y) = \mathcal{A}$.
3. $A_k(x,y) \ge 0$ if and only if $(x,y)$ is on the same side of $X$ with respect to the edge joining $(x_{k-1},y_{k-1})$ to $(x_k,y_k)$.

What this means is for all $(x,y)$, we have $\displaystyle\;\sum_{k=1}^n |A_k(x,y)| \ge \mathcal{A}$.
Furthermore, $X$ is the level set for the absolute value equation $\displaystyle\;\sum_{k=1}^n |A_k(x,y)| = \mathcal{A}\;$.