Conteggio dei poligoni negli arrangiamenti
Per una disposizione delle linee $\cal{A}$nell'aereo, un poligono inducente $P$ è un semplice poligono che soddisfa: (a) ogni bordo $e$ di $P$ si trova su una linea $\ell$ di $\cal{A}$e (b) ogni riga $\ell \in \cal{A}$ è allineato con un bordo $e$ di $P$. Se$P$ ha $k$ bordi e $\cal{A}$ ha $n$ Linee, $k \ge n$. Notare che diversi bordi di$P$ potrebbe trovarsi sulla stessa linea di $\cal{A}$.
È noto che se le linee in $\cal{A}$ sono in posizione generale nel senso che non esistono due linee parallele e non tre linee si incontrano in un punto, quindi $\cal{A}$ha un poligono inducente. 1 Le mie domande riguardano il conteggio dei poligoni induttori.
Q . Su tutti gli accordi$\cal{A}$ di $n$ linee in posizione generale, quali sono i limiti superiore e inferiore del numero di poligoni induttori per $\cal{A}$, e quali accordi raggiungono questi limiti?
Per chiarire (grazie MaxAlekseyev): Let $\cal{A}$ essere una disposizione specifica di $n$ linee in posizione generale. $\cal{A}$supporta un certo numero di poligoni inducenti incongruenti. Quali sono il massimo e il minimo di questo numero, su tutti gli accordi di$n$ Linee?
Altre domande forse più facili si suggeriscono, ad esempio: qualsiasi disposizione ha mai più di un poligono convesso che induce?
Il mio obiettivo originale era trovare un'area minima che induca un poligono, il che è probabilmente difficile.
1 Scharf, Ludmila e Marc Scherfenberg. "Induzione di poligoni di disposizioni di linea." In International Symposium on Algorithms and Computation , pp. 507-519. Springer, Berlino, Heidelberg, 2008. Springer link .
Risposte
Andando al duale geometrico,
- le linee vengono mappate su punti con coordinate polari $(\varphi,\,r)$ dove $\varphi$ è l'angolo della normale, che punta lontano dall'origine, con il positivo $x$-asse e $r$ la distanza dell'origine dalla linea
- coppie di linee intersecanti nel piano euclideo si associano a segmenti di linea che collegano i rispettivi punti doppi.
- gli arrangiamenti di segmenti puntiformi nel doppio piano possono essere interpretati come incorporamenti planari di grafici e semplici disposizioni di linee producono un grafico completo.
Quella semplice disposizione delle linee produce un grafico completo implica che possono sempre essere rappresentate da un singolo poligono: qualsiasi ciclo di Hamilton attraverso i punti nel doppio piano andrà bene.
Le altre domande sembrano trovare risposta dai risultati sui complessi cellulari, alcuni dei quali si trovano nel citato articolo di Wikipedia come ad esempio " Sebbene una singola cella in una disposizione possa essere delimitata da tutte le n linee, in generale non è possibile che m celle diverse essere tutti delimitati da n linee, ma la complessità totale di m celle è al massimo$Θ(m^{2/3}n^{2/3} + n)$, [11] quasi lo stesso limite che si verifica nel teorema di Szemerédi-Trotter sulle incidenze punto-retta nel piano "
$ILP$ formulazione
Se si desidera una corrispondenza uno a uno tra le linee e i lati del poligono, una formulazione di programmazione lineare intera può fornire soluzioni che possono essere soggette a criteri di ottimizzazione desiderabili:
le variabili binarie corrispondono ai bordi creati dividendo le linee nei punti di intersezione, i vincoli sono che le variabili dei bordi collineari si sommano a $1$e che in ogni intersezione di due rette le somme delle variabili corrispondenti ai loro archi adiacenti sono uguali, cioè
se$l_{1i},l_{i1},l_{2,i},l_{i2}$ sono le variabili binarie corrispondenti ai bordi delle linee $L_1$ e $L_2$ che si intersecano nel punto $(x_i,y_i)$, poi $l_{1i}+l_{i1}=l_{2,i}+l_{i2}$ deve essere soddisfatto.
L'imposizione di vincoli di eliminazione del subtour può rispondere all'esistenza di un singolo poligono con biiezione tra i suoi bordi e le linee.