Compter les polygones dans les arrangements
Pour un arrangement de lignes $\cal{A}$dans le plan, un polygone inducteur $P$ est un polygone simple satisfaisant: (a) chaque arête $e$ de $P$ se trouve sur une ligne $\ell$ de $\cal{A}$, et (b) chaque ligne $\ell \in \cal{A}$ est colinéaire avec un bord $e$ de $P$. Si$P$ a $k$ bords et $\cal{A}$ a $n$ lignes, $k \ge n$. Notez que plusieurs bords de$P$ pourrait se trouver sur la même ligne de $\cal{A}$.
On sait que si les lignes $\cal{A}$ sont en position générale en ce sens qu'aucune ligne n'est parallèle et qu'aucune ligne ne se rencontre en un point, alors $\cal{A}$a un polygone inducteur. 1 Mes questions concernent le comptage des polygones inducteurs.
Q . Sur tous les arrangements$\cal{A}$ de $n$ lignes en position générale, quelles sont les limites supérieure et inférieure du nombre de polygones inducteurs pour $\cal{A}$, et quels arrangements atteignent ces limites?
Pour clarifier (merci MaxAlekseyev): Soit $\cal{A}$ être un arrangement spécifique de $n$ lignes en position générale. $\cal{A}$prend en charge un certain nombre de polygones inducteurs incongruents. Quels sont les max et min de ce nombre, sur tous les arrangements de$n$ lignes?
D'autres questions peut-être plus faciles se posent, par exemple: un arrangement a-t-il jamais plus d'un polygone inducteur convexe?
Mon objectif initial était de trouver une zone minimale induisant un polygone, ce qui est probablement difficile.
1 Scharf, Ludmila et Marc Scherfenberg. "Induire des polygones d'arrangements de ligne." Dans International Symposium on Algorithms and Computation , pp. 507-519. Springer, Berlin, Heidelberg, 2008. Lien Springer .
Réponses
Aller au duel géométrique,
- les lignes correspondent à des points avec des coordonnées polaires $(\varphi,\,r)$ où $\varphi$ est l'angle de la normale, pointant loin de l'origine, avec le positif $x$-axis et $r$ la distance de l'origine à la ligne
- des paires de lignes qui se coupent dans la carte du plan euclidien aux segments de ligne reliant les points doubles respectifs.
- Les arrangements de segment de point dans le plan double peuvent être interprétés comme des plongements planaires de graphes et de simples arrangements de lignes donnent un graphe complet.
Cette simple disposition des lignes donne un graphe complet implique qu'elles peuvent toujours être représentées par un seul polygone: n'importe quel cycle de Hamilton passant par les points du plan dual fera l'affaire.
Les autres questions semblent trouver une réponse par les résultats sur les complexes cellulaires, dont certains sont dans l'article de Wikipédia cité comme par exemple " Bien qu'une seule cellule dans un arrangement puisse être délimitée par toutes les n lignes, il n'est pas possible en général pour m cellules différentes de tous sont délimités par n lignes. Au contraire, la complexité totale de m cellules est au plus$Θ(m^{2/3}n^{2/3} + n)$, [11] presque la même borne que celle qui se produit dans le théorème de Szemerédi – Trotter sur les incidences de ligne de point dans le plan "
$ILP$ formulation
Si une correspondance biunivoque entre les lignes et les côtés du polygone est souhaitée, alors une formulation de programmation linéaire entière peut donner des solutions qui peuvent être soumises à des critères d'optimisation souhaitables:
les variables binaires correspondent aux arêtes créées en fractionnant les lignes aux points d'intersection, les contraintes étant que les variables d'arêtes colinéaires se résument à $1$et qu'à chaque intersection de deux lignes les sommes des variables correspondant à leurs arêtes adjacentes sont égales, c'est
-à- dire si$l_{1i},l_{i1},l_{2,i},l_{i2}$ sont la variable binaire correspondant aux bords des lignes $L_1$ et $L_2$ qui se croisent en un point $(x_i,y_i)$, puis $l_{1i}+l_{i1}=l_{2,i}+l_{i2}$ doit être satisfait.
L'imposition de contraintes d'élimination de sous-niveaux peut répondre à l'existence d'un seul polygone avec bijection entre ses arêtes et les lignes.