Cada polígono tiene un interior diagonal

Question

¿Cómo hace uno para demostrar que en cada polígono (con al menos 4 lados, no necesariamente convexa), que es posible dibujar un segmento de un vértice a otro que se encuentra en su totalidad dentro del polígono.

En particular, estoy teniendo problemas para rigurosamente la definición de la "dentro del polígono." Para un polígono convexo, se puede definir el interior como la unión de la mitad de los aviones que son extensiones de los lados. Sin embargo, no estoy seguro de cómo hacer esto para el no-convexas de los polígonos.

Me gustaría hacerlo con el mayor rigor, teniendo en cuenta el polígono como una figura en $\mathbb{R}^2$, en lugar de apelar a la intuición geométrica.

Edit: obviamente, debo especificar nonintersecting.

Answer 1

Me acaba de asistir a la pregunta de interior/exterior. De ello se desprende desde el Jordán de la Curva Teorema que su polígono divide el plano en dos partes, una interior y una (unbounded) en el exterior. Para llegar de uno a otro, insistimos en curvas suaves (o, para el caso, de planta poligonal, de caminos que cruzan el polígono sólo una vez, no en un vértice, y en un ángulo distinto de cero para el segmento cruzado (tangencia).

Como resultado, la prueba simple para interior/exterior, muy complicado de cifras, es iniciar un cierto punto muy lejos de el polígono, trazar una ruta de acceso al punto de interés, y contar el número de veces que el camino cruza el polígono (permitiendo que sólo los tipos de cruce se indicó anteriormente). Si el número de cruces es $0$ o de lo contrario, el punto de interés está fuera del polígono. Si el número de cruces es $1$ o de lo contrario impar, el punto de interés está en el interior del polígono.

EDIT ** SÁBADO: UNA muy buena prueba y la discusión está dada por Joseph O'Rourke, sitio web OROURKE en el Capítulo Uno de su libro el Arte de la Galería de Teoremas y Algoritmos, que se puede descargar en capítulos separados. En el Capítulo Uno, "Polígono de Particiones" en la página 12, hay una rápida prueba para su pregunta, como parte del Teorema 1.2. Tomar tres vértices $v_1, v_2, v_3$ de manera tal que el ángulo es "convexo" con respecto a la poligonal $P$, es decir, un pequeño barrio de $v_2$ dentro del ángulo de $v_1 v_2 v_3$ (exigido por debajo de $\pi$) también se encuentra dentro del polígono $P.$
          
Quizás $v_1 v_3$ es un segmento de línea completamente contenida en $P,$, en cuyo caso hemos terminado. Si no, significa que hay otros vértices del polígono original en el interior del triángulo con vértices $v_1, v_2, v_3.$ Encontrar el vértice, se $x,$ que está en el interior del triángulo y es el más cercano a $v_2,$ distancia se mide sólo en la dirección perpendicular al segmento $v_1 v_3$ (ver Figura 1.13). Como resultado, la línea a través de $x$ y en paralelo a $v_1 v_3$ no pueden cruzarse cualquier otro bordes de $P$ dentro del triángulo $v_1 v_2 v_3.$, En el segmento de $v_2 x$ está completamente dentro de $P.$ . Tenga en cuenta que la medición de distancia para $x$ por completo la distancia Euclídea puede no funcionar correctamente aquí. Sacar algunas fotos! En la página 13, se menciona Meister Dos Orejas Teorema (1975), el Teorema 1.3, que es probablemente el elemento que vio citado.

Evidentemente Meister es G. Meister, "Polígonos tienen oídos," American Mathematical Monthly, volumen 82, páginas 648-651, 1975.

O'Rourke:

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

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

Answer 2

Esto no es del todo riguroso, pero yo sospecho que puede hacerse. Supongamos que nuestro polígono no convexo. A continuación, hay algunos vértice $v_i$ a que el ángulo interior es de más de $\pi$. Considere la posibilidad de la rotación de la ray a través de los puntos de $v_i,v_{i-1}$ a los rayos ir a través de los puntos de $v_i,v_{i+1}$ por el interior del polígono. Ahora, considere el punto en el que este rayo primeros éxitos de los límites del polígono. Esto nos da una función continua a trozos $f \colon (0,\alpha) \to \partial P$ donde $\alpha$ es el ángulo interior en $v_i$. Además, la continua piezas son segmentos de línea. Hemos de probar que existe un vértice en la imagen de $f$. Suponemos que no fue. A continuación, $f(0,\alpha)$ sería un segmento de línea de $v_{i-1}$$v_{i+1}$. Pero esto es una contradicción, porque de la manera que $v_i$ fue el elegido.

Answer 3

La existencia de un interior diagonal es equivalente a la capacidad para triangular los polígonos (que son libres de auto-intersecciones).

Algunos de los algoritmos se describen en la wikipedia:

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

Answer 4

Con el fin de demostrar lo que se llama la Bolyai-Gerwien-Wallace Teorema, que si uno tiene dos plano simple de los polígonos de la misma área, a continuación, se puede cortar el primer polígono en un número finito de polígonos simples y volver a montar las piezas (de rompecabezas de estilo) en el otro polígono, Larwrence Levy en el libro Geomety: la Matemática Moderna a través del plano Euclidiano (Prindle, Weber & Schmidt, 1970) primero hace una prueba (p. 142-143) que cualquier plano simple polígono puede ser triangulados con el hecho (con pruebas) de que uno puede encontrar dos vértices (no extremos de una arista de un polígono simple que puede ser acompañado por un segmento de la línea de la mentira (excepto para sus fines) totalmente en el interior del polígono.