Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

How does one prove that in every polygon (with at least 4 sides, not necessarily convex), that it is possible to draw a segment from one vertex to another that lies entirely inside the polygon.

In particular, I'm having trouble rigorously defining the "inside of polygon." For a convex polygon, one can define the inside as the union of half-planes that are extensions of the sides. However, I'm not sure how to do this for the non-convex polygons.

I'd like to do this rigorously, considering the polygon as a figure in $\mathbb{R}^2$, instead of appealing to geometric intuition.

Edit: obviously, I need to specify nonintersecting.

share|improve this question
    
Seen this? –  J. M. Nov 19 '11 at 8:25
    
Alright, instead of asking people to look stuff up on Wikipedia, I vote that every time this comes up, we delete the relevant Wikipedia page. –  Will Jagy Nov 19 '11 at 8:31
    
Potato, I looked at the link provided by lhf in a comment to the answer by zyx. That page is on a website of David Eppstein at U. C. Irvine. That led me to the page of Joseph O'Rourke and a good, basic, book. I am commenting as you will thereby receive notice on MSE of changes to your query. By itself, you would not be notified of edits I made to my own answer. –  Will Jagy Nov 19 '11 at 22:26
    
Thanks for the reference, Will! –  Potato Nov 20 '11 at 2:11

4 Answers 4

up vote 6 down vote accepted

I will just attend to the question of inside/outside. It follows from the Jordan Curve Theorem that your polygon splits the plane into two parts, an inside and an (unbounded) outside. To get from one to the other, we insist on smooth curves (or, for that matter, polygonal paths) that cross the polygon only once, not at a vertex, and at a nonzero angle to the segment crossed (tangency not allowed).

As a result, the simple test for inside/outside, for extremely convoluted figures, is to start a some point very far from the polygon, draw a path to the point of interest, and count the number of times the path crosses the polygon (permitting only the types of crossing indicated above). If the number of crossings is $0$ or otherwise even, the point of interest is outside the polygon. If the number of crossings is $1$ or otherwise odd, the point of interest is inside the polygon.

EDIT ** SATURDAY: A very good proof and discussion is given by Joseph O'Rourke, website OROURKE in Chapter One of his book Art Gallery Theorems and Algorithms, which one may download as separate chapters. In Chapter One, "Polygon Partitions," page 12, there is a quick proof for your question, as part of Theorem 1.2. Take three consecutive vertices $v_1, v_2, v_3$ such that the angle is "convex" with regard to the polygon $P$, that is, a tiny neighborhood of $v_2$ inside the angle $v_1 v_2 v_3$ (demanded below $\pi$) is also inside the polygon $P.$
          Diagonal proof
Perhaps $v_1 v_3$ is a line segment completely contained in $P,$ in which case we are done. If not, it means there are other vertices of the original polygon inside the triangle with vertices $v_1, v_2, v_3.$ Find the vertex, call it $x,$ that is inside the triangle and is closest to $v_2,$ distance measured only in the direction perpendicular to segment $v_1 v_3$ (see Figure 1.13). As a result, the line through $x$ and parallel to $v_1 v_3$ can not intersect any other edges of $P$ inside the triangle $v_1 v_2 v_3.$ Then the segment $v_2 x$ is completely inside $P.$ . Note that measuring distance for $x$ by full Euclidean distance may not work properly here. Draw some pictures! On page 13, he mentions Meister's Two Ears Theorem (1975), Theorem 1.3, which is probably the item you saw quoted.

Evidently Meister is G. Meister, "Polygons have ears," American Mathematical Monthly, volume 82, pages 648-651, 1975.

O'Rourke:

http://math.stackexchange.com/users/237/joseph-orourke

http://mathoverflow.net/users/6094/joseph-orourke

share|improve this answer
    
I see how this provides an easy test for individual points. However, the case of a line seems harder. –  Potato Nov 19 '11 at 8:31
    
Yes, of course. Why do you believe that it is always possible to draw your interior segment, between vertices, with at least four sides? –  Will Jagy Nov 19 '11 at 8:35
    
I'll assume your last clause should be "for every every polygon with at least four sides." I saw in a math book the fact that "every polygon with at least 4 sides has an interior diagonal" stated without proof. –  Potato Nov 19 '11 at 8:38
2  
Thank you, Will! I added the figure that makes it clearer. I'm embarrassed to say this proof is not only in the book Will cited, but also in the two later books, Computational Geometry in C and in Discrete and Computational Geometry. –  Joseph O'Rourke Nov 20 '11 at 22:26
1  
@JosephO'Rourke, BTW, it's not too late to say it: your newest book is great, both text and figures! –  lhf Apr 12 '12 at 11:50

This is not entirely rigorous but I suspect it can made such. Suppose that our polygon is not convex. Then there is some vertex $v_i$ at which the interior angle is over $\pi$. Consider rotating the ray going through points $v_i,v_{i-1}$ to the ray going through points $v_i,v_{i+1}$ through the interior of the polygon. Now consider the point at which this ray first hits the boundary of the polygon. This gives us a piecewise continuous function $f \colon (0,\alpha) \to \partial P$ where $\alpha$ is the interior angle at $v_i$. Moreover the continuous pieces are line segments. We have to prove that there is a vertex in the image of $f$. Assume there was not. Then $f(0,\alpha)$ would be a line segment from $v_{i-1}$ to $v_{i+1}$. But this is a contradiction because of the way $v_i$ was chosen.

share|improve this answer
    
Looks good to me. It shows that every concave vertex is the end-point of such an interior line segment. It might be simpler to say: The only way that the ray can change which edge of the polygon that it meets is by hitting a vertex. –  TonyK Nov 19 '11 at 9:58

Existence of an interior diagonal is equivalent to the ability to triangulate polygons (that are free of self-intersections).

Some algorithms are described at wikipedia:

http://en.wikipedia.org/wiki/Polygon_triangulation

share|improve this answer
    
See also ics.uci.edu/~eppstein/junkyard/godfried.toussaint.html for a proof that diagonals exist. –  lhf Nov 19 '11 at 10:59

In order to prove what is called the Bolyai-Gerwien-Wallace Theorem, that if one has two plane simple polygons of the same area then one can cut the first polygon into a finite number of simple polygons and reassemble the pieces (jigsaw puzzle style) into the other polygon, Larwrence Levy in the book Geomety: Modern Mathematics via the Euclidean plane (Prindle, Weber & Schmidt, 1970) first gives a proof (p. 142-143) that any plane simple polygon can be triangulated using the fact (with proof) that one can find two vertices (not ends of an edge) of a simple polygon which can be joined by a line segment lying (except for its ends) totally in the interior of the polygon.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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