Buscar este blog

Cargando...

lunes, 21 de mayo de 2012

Poligonos concavos y convexos

Un polígono cóncavo es una de las figuras geometricas mas interesantes que he visto y por supuesto un polígono de este tipo no es convexo.

Un polígono simple es cóncavo si y sólo si al menos uno de sus ángulos internos es mayor que 180 grados. Un ejemplo de un no-simple (auto-intersección) polígono es un polígono estrella.

Un polígono cóncavo debe tener al menos cuatro lados.

poligono concavo y convexo
Un polígono plano es convexo si contiene todos los segmentos de línea que conecta cualquier par de sus puntos. Así, por ejemplo, un pentágono regular es convexo (figura izquierda), mientras que una sangría pentágono no es (figura derecha). Un polígono planar que no es convexo se dice que es un polígono cóncavo.

Deja que un polígono simple tiene n vértices x_i para i = 1, 2, ..., n, y definir los vectores de borde como



Donde  x_(n+1) esta entendido que equivale a x_1. Entonces el poligono eEntonces, el polígono es convexo si y sólo si todo se vuelve de un vector de borde a la siguiente tiene el mismo sentido. Por lo tanto, un polígono simple es convexa si y sólo si

 v_i^_|_·v_(i+1)  

tiene el mismo signo para todo i, donde a^_|_·b denota el producto escalar perp (Hill, 1994). Sin embargo, un ensayo más eficiente que no requiere un conocimiento a priori que el polígono es simple es conocido (Moret y Shapiro 1991).

El problema tiene un final feliz si considera convexo n-polígonos y el número mínimo de puntos de   f(n) (en la posición general) n el que un convexo de n-gon can always siempre puede encontrarse. La respuesta para n=3, 4, 5, y 6 son 3, 5, 9, y 17. Su conjetura es f(n)=2^(n-2)+1,

pero solo se puede probar con
 2^(n-2)<=f(n)<=(2n-4; n-2),

Donde  (n; k) es un coeficiente binomial.

No hay comentarios:

Publicar un comentario en la entrada

Blogger news