Why is Unit Circle Including Its Interior not a Polyhedron

Question

I'm in a linear programming class and I'm trying to understand why the unit circle with its interior is not a polyhedron.

I know there is a proof by contradiction that the unit circle not including its interior is not a polyhedron. But I'm wondering why if we include the interior, the set is still not a polyhedron. What is the intuition behind why such a circle is not a polyhedron? Does it have to do with the fact that a circle has an infinite amount of extreme points? The set in consideration is actually $$\{(x,y) \in \mathbb{R}^2 ; x^2+y^2 \leq 1, x \geq 0, y \geq 0\},$$ and my definition of polyhedron is a set which is the intersection of finitely many half-planes.

Answer 1

Let me use the standard terminology disc to refer to a circle union its interior. Also, let me use the standard terminology polygon to refer to a polyhedron in the plane.

Each circle is the boundary of its corresponding disc, and that boundary has the following special relation with the center point of the disc:

1. Given a disc, its center is equidistant from all points on its boundary.

On the other hand,

2. Given a polygon, there does not exist any point in the plane which is equidistant from all points on its boundary.

Once you are convinced of the truth of 2, then it is clear that a circle is not a polygon, because they do not satisfy the same geometric properties.

To prove 2, one may apply the fact that the boundary of a polygon is a union of finitely many line segments, such that any two of those segments are either disjoint or intersect only at a common endpoint.

Applying that fact, all that remains in order to prove 2 is to prove that for any given line segment, there does not exist any point in the plane which is equidistant from all points on that line segment. I will leave this final proof as an exercise that is easily solved with coordinate geometry (and easily solved with axiomatic Euclidean geometry as well).

Answer 2

Presumably you are using the Euclidean norm. (The unit ball with the $l_1, l_\infty$ norms are polyhedral.)

The Euclidean norm is strictly convex, so if $a \neq b$ then $\|ta+(1-t)b\|^2 < t \|a\|^2+(1-t)\|b\|^2$ for $t \in (0,1)$.

In particular, if $\|a\| \le 1, \|b\| \le 1$ and $a \neq b$, then $\|ta+(1-t)b\|^2 < 1$ for $t\in (0,1)$.

Suppose $P$ is a polyhedron and $P \subset \bar{B}$, the closed unit ball. Then $\bar{B} \setminus P$ is non empty and so we cannot express $\bar{B}$ as a polyhedron. To see this, consider the following:

Any compact polyhedron can be written as the convex hull of a finite number of points, so we can write $P = \operatorname{co} \{ x_1, \cdots , x_m\}$. We can assume that none of the points can be written as a convex combination of the remaining points. We must have $\|x_k\| \le 1$.

Any point $x \in P \setminus \{ x_1, \cdots , x_m\}$ can be written as $x = \sum_k t_k x_k$, with $t_k < 1$ and $\sum_k t_k = 1$.

Then $x = t_1 x_1 + (1-t_1) \sum_{k \neq 1} {t_k \over 1-t_1} x_k$ and since $\|x_1\| \le 1$ and $\| \sum_{k \neq 1} {t_k \over 1-t_1} x_k \| \le 1$, we see that $\|x\| < 1$.

In particular, the only points in $P$ that have norm one are $x_1,...,x_p$. Hence $P$ cannot equal $\bar{B}$.

Answer 3

We shall a give a proof which is (hopefully) intuitive but can be made precise if desired.

The "unit circle with its interior" is the set $D = \{(x,y) \in \mathbb{R}^2 ; x^2+y^2 \leq 1 \}$. Its boundary is the unit circle $C = \{(x,y) \in \mathbb{R}^2 ; x^2+y^2 = 1 \}$.

For each $c \in \mathbb R^2 \setminus \{ 0 \}$ let $L'(c)$ be the line line through $0$ and $c$, and $L(c)$ denote the line through $c$ which is perpendicular to $L'(c)$. By $H(c) $ we denote the half-plane which has $L(c)$ as its boundary and contains $0$. Clearly each half-plane $H$ with $0 \in H$ whose boundary line $L$ does not contain $0$ has the form $H = H(c)$ for a unique $c$. In fact, let $L'$ be the line through $0$ which is perpendicular to $L$ and let $c$ be the intersection point of $L$ and $L'$. Then $H = H(c)$.

Assume that $D$ is the intersection $I(c_1,\ldots,c_n)$ of finitely many half-planes $H(c_1),\ldots, H(c_n)$.

W.l.o.g. we may assume that all $c_i \in C$. In fact, the line $L'(c_i)$ intersects $C$ in a point $c^*_i$ between $0$ and $c_i$ ($c^*_i = c_i$ is possible). Then we have $D \subset H(c^*_i) \subset H(c_i)$ so that $I(c_1,\ldots,c_n) = I(c^*_1,\ldots,c^*_n)$. Note that the boundary line $L(c^*_i)$ of $H(c^*_i)$ is the tangent to $C$ at $c^*_i$.

If we add finitely points $c_i \in C$, $i= n+1,\ldots,m$, then clearly $I(c_1,\ldots,c_n) = I(c_1,\ldots,c_m)$. We may therefore w.l.o.g. assume that the points $(0,1)$ and $(1,0)$ belong to the $c_i$ and that the $c_i$ are pairwise distinct.

W.l.o.g. we may assume that $c_1 = (0,1)$ and $c_2$ is the first point reached if we travel counterclockwise along $C$ starting at $c_1$. The point $c_2$ lies on the quarter circle between $(1,0)$ and $(0,1)$. The lines $L_1 = L(c_1)$ and $L(c_2)$ intersect in a point $p$ lying on the line segment between $(1,0)$ and $(1,1)$. Clearly, $p \in H(c_1) \cap H(c_2)$, but $p \notin D$.

Any half-plane $H(c)$ where $c \in C$ does not belong to the arc between $c_1$ and $c_2$ contains $p$. This is intuitively clear: When we move counterclockwise along $C$ from $c_2$ to $(-1,0)$, then the intersection point $p_c$ of $L_1$ and $L(c)$ moves on $L_1$ from $p$ to $\infty$ and the half-line $L_1^-(p_c) \subset L_1)$ below $p_c$ (which has the property $p_c \in L_1^-(p_c)$) is contained in $H(c)$. When we reach $(-1,0)$, then $L_1$ and $L(-1,0)$ are parallel (i.e. do not intersect) and trivially $p \in H(-1,0)$. When we move further from $(-1,0)$ to $(1,0)$, the intersection point $p_c$ moves on $L_1$ from $-\infty$ to $(1,0)$ and the half-line $L_1^+(p_c) \subset L_1$ above $p_c$ (which has the property $p \in L_1^+(p_c)$) is contained in $H(c)$.

You should draw a picture - everything can be made absolutely precise if desired.

This shows that $p \in \bigcap_{i=1}^n H(c_i)$ which is a contradiction.