Dibujar curvas (o segmentos) que no se intersecan conectando vértices no adyacentes en un polígono regular

Si puede usar curvas fuera del polígono, el problema sería el mismo que unir vértices no adyacentes en un polígono esférico. Puede hacerlo en el "exterior" y el "interior", y obtener un máximo de$2(n-3)$se une y en ese punto la esfera se divide en triángulos topológicos y no es posible más unión.

Todavía tiene que usar curvas, en lugar de líneas rectas (es decir, geodésicas/grandes círculos), porque a veces las líneas geodésicas se verán obligadas a cruzarse. Consulte la Columna de geometría computacional 51 de Joseph O'Rourke para ver una ilustración de cómo las geodésicas no funcionan.

Aquí hay una prueba teórica de grafos que puedes dibujar como máximo$2(n-3)$diagonales Dejar$G$sea ​​un grafo cuyos vértices sean los$n$vértices del polígono y cuyas aristas son los lados y las curvas que dibujamos. Suponer$G$tiene$m$bordes (por lo tanto, el número de curvas diagonales dibujadas es$m-n$). Dejar$f$indican el número de regiones conectadas dentro y fuera del polígono (tanto regiones limitadas como ilimitadas).

Tenga en cuenta que$G$es un gráfico plano. Por la fórmula de Euler,

$$n-m+f=2\,.$$ Ahora, cada región conectada tiene un límite formado por al menos tres bordes. Cada borde bordea exactamente dos regiones. De este modo, $$3f\leq 2m\text{ or }f\leq \frac{2}{3}\,m\,.$$ Por eso, $$2=n-m+f\leq n-m+\dfrac{2}{3}\,m=n-\frac13\,m\,.$$ Esto significa $$m\leq 3(n-2)=3n-6\,.$$ Por eso, $$m-n\leq (3n-6)-n=2n-6=2(n-3)\,.$$ Es fácil ver eso$2(n-3)$Se pueden dibujar segmentos. Vea la respuesta de brainjam para ver un ejemplo.