Das Schneid-Lemma (auch bekannt als Zellzerlegungs-Lemma) besagt, dass es bei Linien in der Ebene möglich ist, es für jede 1 ≤ r ≤ n in O ( r 2 ) -Regionen (sogar Dreiecke) zu unterteilen, so dass das Innere jeder Region geschnitten wird durch O ( n / r ) Linien. Weitere Informationen finden Sie beispielsweise in Matouseks Buch Lectures on Discrete Geometry oder in diesem Beitrag .
Meine Frage ist, ob die Ebene durch -Linien (in O ( r 2 ) -Regionen) unterteilt werden kann, so dass das Innere einer Region von O ( n / r ) der ursprünglichen Linien geschnitten wird .
co.combinatorics
cg.comp-geom
domotorp
quelle
quelle
Antworten:
Nehmen wir also an, Sie bauen Ihre vertikale Zerlegung auf, indem Sie die -Linien nehmen, ihre Anordnung nehmen und dann ihre vertikale Zerlegung berechnen. Die Frage ist, ob es eine Menge von O ( r ) -Linien der ursprünglichen Reihe von Linien gibt, so dass diese vertikale Zerlegung einen 1 / r- Schnitt bildet.O ( r ) O (r ) 1 / r
Wenn Sie nun Noga Alons Konstruktion in diesem Artikel betrachten:
www.math.tau.ac.il/~nogaa/PDFS/epsnet3.pdf
Wenn Sie es verdoppeln, erhalten Sie eine Reihe von Linien. Wenn ein Punkt in mehr als Linien enthalten ist, muss eine der Linien zum 1 / r- Netz der Linien gehören. Diese Konstruktion zeigt jedoch, dass jedes Netz in O ( r ) eine streng superlineare Größe haben muss . Das Ergebnis von Noga gilt auch für die schwache ϵ -net-Version. Dies zeigt, dass es keine Zeilen gibt, die die gewünschte Eigenschaft hätten.n / r 1 / r O ( r ) ϵ
quelle
quelle