2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Question has been edited $\endgroup$ – forreal Sep 27 '19 at 5:02
  • 1
    $\begingroup$ A polyhedron has faces that are polygons, so has to be 3 dimensional, which a disk is not. And a polygon has to have edges that are straight lines, which a disk does not have. $\endgroup$ – Heath Winning Sep 27 '19 at 5:09
  • $\begingroup$ A bounded polyhedron is the convex hull of a finite set; a finite subset of the plane has a conventional $n$-sided polygon as its convex hull, not a disc. $\endgroup$ – Lord Shark the Unknown Sep 27 '19 at 5:16
  • $\begingroup$ This has been discussed on many other threads. Here are a few of the best. For general discussion: math.stackexchange.com/q/31785 For the formal difficulties of going down the limit path: math.stackexchange.com/a/1164990 For the most generous interpretation, using nonstandard analysis: math.stackexchange.com/a/1644477 $\endgroup$ – Chris Culter Sep 27 '19 at 5:23
  • 1
    $\begingroup$ The unit disk cannot be expressed as the intersection of a finite number of half spaces. $\endgroup$ – copper.hat Sep 27 '19 at 6:36
2
$\begingroup$

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,

  1. 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).

$\endgroup$
1
$\begingroup$

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.

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 > 0$ 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}$.

$\endgroup$
  • $\begingroup$ This invokes the fact that a bounded set which is the intersection of finitely many half-planes is the convex hull of a finite number of points. $\endgroup$ – Paul Frost Sep 28 '19 at 9:57
  • $\begingroup$ You need closure as well. That is why I mentioned compact above. $\endgroup$ – copper.hat Sep 28 '19 at 14:00
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.