2 Dada una lista de \( n\geq 1 \) vértices en el plano cartesiano \( \{(a_0,b_0),(a_1,b_1),\ldots,(a_n,b_n)\} \) determine si, al considerar los elementos de la lista como vértices consecutivos del perímetro de una figura geométrica, la figura en cuestión es un polígono. Y, cuando éste sea el caso, decidir si es un polígono convexo.
Una lista de más de dos puntos siempre define un polígono, Supongo que se trata de ver si es cruzado o simple (si sus lados se intersecan o no). Para ello debe comprobarse, por ejemplo, si cada segmento constituido por cada par de puntos consecutivos de la lista se interseca con los segmentos que le siguen o no, saltándose el inmediatamente siguiente. El número de comprobaciones es entonces \( \displaystyle\sum_{k=1}^{n-2}{n-k-1}=\displaystyle\sum_{k=1}^{n-2}k=\displaystyle\frac{(n-2)(n-1)}{2}=\frac{1}{2}n^2 - \frac{3}{2}n + 1 \). En el caso del primer segmento, puede saltarse la comprobación con el último (que es su anterior en orden cíclico). Se debe, más que se puede, por lo que se dice a continuación.
¿En que debe consistir cada una de estas comparaciones? Se trata de ver que al menos uno de los dos segmentos está enteramente en uno de los semiplanos definido por el otro segmento, pues uno podría cortar a la prolongación del otro, pero entonces el segundo no puede cortar a la prolongación del primero sin que se corten los propios segmentos.
Si los dos segmentos son \( [A, B]\textrm{ y }[C, D] \), distintos si el polígono ha de ser simple, sean \( \vec{a}, \vec{b}, \vec{c}\textrm{ y }\vec{d} \) sus vectores de posición con cualquier origen.
Lo mejor para evitar divisiones o el uso de funciones trigonométricas es utilizar el producto vectorial. Como todos los vectores están incluidos en el plano Oxy, podemos considerarlos vectores de \( \mathbb{R}^3 \) con la tercera componente nula. Su producto vectorial tendrá entonces a lo suma la tercera componente distinta de cero. En lo sucesivo, al hablar del signo del producto vectorial, me refiero al signo de esta tercera componente.
Debe comprobarse que \( (\vec{b}-\vec{a})\times\vec{c} \) tiene el mismo signo que \( (\vec{b}-\vec{a})\times\vec{d} \) o que \( (\vec{d}-\vec{c})\times\vec{a} \) tiene el mismo signo que \( (\vec{d}-\vec{c})\times\vec{b} \), no contando como de igual signo cuando uno de ellos es cero.
Seben realizarse entonces del orden de \( 2n^2 \) productos vectoriales, \( n^2 \) comparaciones y \( \displaystyle\frac{n^2}{2} \) disyunciones, entre otras cosas.
Para ver si es convexo, basta con ver que los vectores consecutivos, que unen puntos consecutivos con el inicio del segundo coincidiendo con el extremo del primero, siempre giran en el mismo sentido, viendo que sus productos vectoriales tienen todos el mismo signo. Por tanto \( n \) productos vectoriales. Puede simultanearse con la comprobación de que el polígono es no cruzado.
Bueno, esto es un esbozo, tienes que detallarlo ...
Saludos,
