4 votos

Más grande de un Triángulo Equilátero en un Polígono

Existe un algoritmo para determinar el mayor triángulo equilátero en un polígono convexo?

1voto

yoliho Puntos 340

Sí, existe un algoritmo:

DePano, A., Yan Ke, y J. O'Rourke. "El descubrimiento más grande inscrito triángulos equiláteros y plazas". Proc. 25 de Allerton Conf. Commun. Control De Comput. 1987.

Por desgracia, no tengo fácil acceso a mi propio artículo. :-/


      EqTriSquare(Imagen de este enlace.)

0voto

NovaDenizen Puntos 2578

Mi hipótesis inicial de que está mal, y un 80-80-20 triángulo proporciona la coutnerexample.


Si el triángulo es máxima, a continuación, todos los 3 vértices tiene que estar en los bordes del polígono. Así que estoy pensando que no tiene sentido abordar el problema de iterar sobre todas las tuplas de 3 aristas (filtrado de tuplas, donde todos 3 los bordes son de la misma), suponiendo un vértice está en algún lugar en cada uno de estos bordes, y la búsqueda de soluciones mediante el uso de cada tupla de bordes.

Dicen $x_1$, $x_2$, y $x_3$, son los vértices de un triángulo equilátero.

Si $x_i$ es constreñido a estar en un segmento de línea entre el$p_i$$q_i$, $x_i = p_i \alpha_i + (1 - \alpha_i)q_i$ donde $0 \le \alpha_i \le 1$ es una interpolación de variables que pone a cada una de las $x_i$ en una proporción de $\alpha_i$ a lo largo de cada segmento de línea.

Definir $v_1$, $v_2$, y $v_3$ como el vector de los bordes de este triángulo ($v_1 = x_1 - x_2$, $v_2 = x_2 - x_3$, $v_3 = x_3 - x_1$). Tenemos $v_1 \cdot v_1 = v_2 \cdot v_2 = v_3 \cdot v_3$ ya que las longitudes de los lados deben ser iguales. Sustituir las definiciones de $v_i$ en estas ecuaciones, a continuación, sustituir la interpolación de las ecuaciones de $x_i$ por encima de eso.

Ahora que las ecuaciones se ven como $P_1(\alpha_1, \alpha_2, \alpha_3) = P_2(\alpha_1, \alpha_2, \alpha_3) = P_3(\alpha_1, \alpha_2, \alpha_3)$ donde cada una de las $P_i$ es un 2º grado multinomial. Todas las soluciones de estos multinomials obedecer la $\alpha$ rango de requisito de forma de triángulos equiláteros de tocar el borde del polígono.

Cualquier instancia en particular de estas ecuaciones puede tener 0, 1 o 2 soluciones, tal vez algún otro número, y, posiblemente, una infinita gama de soluciones (como un regular (o suficientemente simétrica) polígono con 3n de los bordes). Si usted encuentra un número finito de soluciones que usted puede simplemente prueba a ver que resultados en el mayor tamaño de borde. Si usted encuentra una infinita gama de soluciones, a continuación, encontrar una máxima triángulo es más complicado.

~~

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by: