Divide un cuadrado con polígonos convexos. ¿Cuál es el número máximo de aristas?

Question

Dado un cuadrado que se divide en polígonos convexos tal que $n$ regiones se crean. ¿Cuál es la maxmimal número de aristas en una partición?

Ejemplo.

Las dos plazas a continuación ambos tienen $n=4$ regiones, pero el de la izquierda tiene 8 aristas y el otro tiene 12 aristas. Así que en este caso 12 bordes es máxima.

Yo tengo tengo una observación: cada cara está limitada por al menos 3 de los bordes. Sin embargo, ¿cómo puedo pasar de ahí?

Answer 1

Si hay $n$ convexa de las regiones en el interior de la plaza, hay $n+1$ regiones total contando el fuera de la región (que no es convexo).

Excepto por las cuatro esquinas de la plaza, cada vértice debe tener grado mínimo de $3$: un vértice de grado $2$ subdivide un borde entre dos regiones, y si son convexos, entonces el límite entre la continuación, sólo puede ser una línea recta (de modo que el vértice no existiría).

Así que si hay $v$ vértices, entonces el grado de la suma es, al menos, $3v - 4$, así que hay al menos $\frac32v - 2$ bordes.

Por la fórmula de Euler, $v - e + f = 2$, lo $v = e-f+2 = e-(n+1)+2 = e-n+1$. Sustituyendo esto en $e \ge \frac32v - 2$rendimientos $$ e \ge \frac32(e-n+1)-2 \implica e \le 3n+1. $$

Por lo tanto, pueden ser en la mayoría de las $3n+1$ bordes.

Una forma de lograr esto es para poner $n-1$ bordes verticales, la separación de la plaza en $n$ tiras finas. A continuación, la parte superior e inferior de los laterales de la plaza se compone de $n$ bordes de cada uno, y los lados izquierdo y derecho son también cada uno de los bordes, dándonos $(n-1)+2n+2 = 3n+1$ bordes.