Contando polígonos en arreglos
Para un arreglo de líneas $\cal{A}$en el plano, un polígono inductor $P$ es un polígono simple que satisface: (a) cada borde $e$ de $P$ se encuentra en alguna línea $\ell$ de $\cal{A}$, y (b) cada línea $\ell \in \cal{A}$ es colineal con un borde $e$ de $P$. Si$P$ tiene $k$ bordes y $\cal{A}$ tiene $n$ líneas, $k \ge n$. Tenga en cuenta que varios bordes de$P$ podría estar en la misma línea de $\cal{A}$.
Se sabe que si las líneas en $\cal{A}$ están en posición general en el sentido de que no hay dos líneas paralelas y no hay tres líneas que se encuentran en un punto, entonces $\cal{A}$tiene un polígono inductor. 1 Mis preguntas se refieren a contar los polígonos inductores.
Q . Sobre todos los arreglos$\cal{A}$ de $n$ líneas en posición general, ¿cuáles son los límites superior e inferior en el número de polígonos inductores para $\cal{A}$y ¿qué arreglos alcanzan esos límites?
Para aclarar (gracias MaxAlekseyev): Deja $\cal{A}$ ser un arreglo específico de $n$ líneas en posición general. $\cal{A}$admite un cierto número de polígonos inductores incongruentes. ¿Cuáles son el máximo y el mínimo de este número, en todos los arreglos de$n$ ¿líneas?
Se sugieren otras preguntas posiblemente más fáciles, por ejemplo: ¿Alguna disposición tiene más de un polígono inductor convexo?
Mi objetivo original era encontrar un polígono inductor de área mínima, lo que probablemente sea difícil.
1 Scharf, Ludmila y Marc Scherfenberg. "Inducción de polígonos de arreglos de líneas". En Simposio Internacional sobre Algoritmos y Computación , págs. 507-519. Springer, Berlín, Heidelberg, 2008. Springer link .
Respuestas
Yendo al dual geométrico,
- mapa de líneas a puntos con coordenadas polares $(\varphi,\,r)$ dónde $\varphi$ es el ángulo de la normal, apuntando lejos del origen, con el positivo $x$-eje y $r$ la distancia del origen a la línea
- pares de líneas que se cruzan en el mapa plano euclidiano a segmentos de línea que conectan los respectivos puntos duales.
- Los arreglos de puntos y segmentos en el plano dual pueden interpretarse como incrustaciones planas de gráficos y arreglos simples de líneas producen un gráfico completo.
Esa simple disposición de líneas produce un gráfico completo implica que siempre se pueden representar mediante un solo polígono: cualquier ciclo de Hamilton a través de los puntos en el plano dual servirá.
Las otras preguntas parecen estar respondidas por resultados sobre complejos celulares, algunos de los cuales se encuentran en el artículo citado de wikipedia como, por ejemplo, " Aunque una sola celda en un arreglo puede estar delimitada por todas las n líneas, no es posible en general todos estar delimitados por n líneas. Más bien, la complejidad total de m celdas es como máximo$Θ(m^{2/3}n^{2/3} + n)$, [11] casi el mismo límite que ocurre en el teorema de Szemerédi-Trotter sobre las incidencias de la línea de puntos en el plano "
$ILP$ formulación
Si se desea una correspondencia uno a uno entre las líneas y los lados del polígono, entonces una formulación de programación lineal entera puede producir soluciones que pueden someterse a los criterios de optimización deseables:
las variables binarias corresponden a los bordes creados al dividir las líneas en los puntos de intersección, siendo las restricciones que las variables de los bordes colineales suman $1$y que en cada intersección de dos líneas las sumas de las variables correspondientes a sus bordes adyacentes son iguales, es decir,
si$l_{1i},l_{i1},l_{2,i},l_{i2}$ son la variable binaria correspondiente a los bordes de las líneas $L_1$ y $L_2$ que se cruzan en el punto $(x_i,y_i)$, luego $l_{1i}+l_{i1}=l_{2,i}+l_{i2}$ debe estar satisfecho.
La imposición de restricciones de eliminación de subtour puede responder a la existencia de un solo polígono con biyección entre sus bordes y las líneas.