Contando polígonos em arranjos
Para um arranjo de linhas $\cal{A}$no plano, um polígono indutor $P$ é um polígono simples que satisfaz: (a) todas as arestas $e$ do $P$ encontra-se em alguma linha $\ell$ do $\cal{A}$, e (b) cada linha $\ell \in \cal{A}$ é colinear com uma borda $e$ do $P$. E se$P$ tem $k$ bordas e $\cal{A}$ tem $n$ linhas, $k \ge n$. Observe que várias arestas de$P$ pode estar na mesma linha de $\cal{A}$.
Sabe-se que se as linhas em $\cal{A}$ estão na posição geral, no sentido de que não há duas linhas paralelas e nem três linhas se encontram em um ponto, então $\cal{A}$tem um polígono indutor. 1 Minhas perguntas dizem respeito à contagem dos polígonos indutores.
Q . Acima de todos os arranjos$\cal{A}$ do $n$ linhas na posição geral, quais são os limites superior e inferior do número de polígonos indutores para $\cal{A}$, e quais arranjos alcançam esses limites?
Para esclarecer (obrigado MaxAlekseyev): Vamos $\cal{A}$ ser um arranjo específico de $n$ linhas em posição geral. $\cal{A}$suporta um certo número de polígonos indutores incongruentes. Quais são o máximo e o mínimo deste número, em todos os arranjos de$n$ linhas?
Outras questões possivelmente mais fáceis surgem, por exemplo: algum arranjo já tem mais de um polígono indutor convexo?
Meu objetivo original era encontrar uma área mínima para induzir o polígono, o que é provavelmente difícil.
1 Scharf, Ludmila e Marc Scherfenberg. "Induzindo polígonos de arranjos de linha." In International Symposium on Algorithms and Computation , pp. 507-519. Springer, Berlin, Heidelberg, 2008. Link Springer .
Respostas
Indo para o dual geométrico,
- linhas mapeiam para pontos com coordenadas polares $(\varphi,\,r)$ Onde $\varphi$ é o ângulo do normal, apontando para longe da origem, com o positivo $x$-eixo e $r$ a distância da origem à linha
- pares de linhas que se cruzam no plano euclidiano são mapeados para segmentos de linha conectando os respectivos pontos duais.
- arranjos de segmento de ponto no plano dual podem ser interpretados como embeddings planares de gráficos e arranjos simples de retas produzem um gráfico completo.
Esse arranjo simples de linhas produz um gráfico completo, implica que elas sempre podem ser representadas por um único polígono: qualquer ciclo de Hamilton através dos pontos no plano dual servirá.
As outras questões parecem ser respondidas por resultados sobre complexos de células, alguns dos quais estão no artigo citado da Wikipedia como, por exemplo, " Embora uma única célula em um arranjo possa ser limitada por todas as n linhas, não é possível em geral para células diferentes todos são limitados por linhas n. Em vez disso, a complexidade total das células m é no máximo$Θ(m^{2/3}n^{2/3} + n)$, [11] quase o mesmo limite que ocorre no teorema de Szemerédi-Trotter em incidências ponto-linha no plano "
$ILP$ formulação
Se uma correspondência de um para um entre as linhas e os lados do polígono for desejada, uma formulação de programação linear inteira pode produzir soluções que podem ser submetidas aos critérios de otimização desejáveis:
as variáveis binárias correspondem às arestas criadas pela divisão das linhas nos pontos de interseção, as restrições sendo que as variáveis das arestas colineares somam $1$e que em cada intersecção de duas linhas as somas das variáveis correspondentes às suas arestas adjacentes são iguais, ou seja,
se$l_{1i},l_{i1},l_{2,i},l_{i2}$ são as variáveis binárias correspondentes às bordas das linhas $L_1$ e $L_2$ que se cruzam no ponto $(x_i,y_i)$, então $l_{1i}+l_{i1}=l_{2,i}+l_{i2}$ deve ser satisfeito.
A imposição de restrições de eliminação de subtour pode responder à existência de um único polígono com bijeção entre suas bordas e as linhas.