Stimmt das Schnitt-Lemma mit O (r) -Linien?

8

Das Schneid-Lemma (auch bekannt als Zellzerlegungs-Lemma) besagt, dass es bei Linien in der Ebene möglich ist, es für jede in -Regionen (sogar Dreiecke) zu unterteilen, so dass das Innere jeder Region geschnitten wird durch Linien. Weitere Informationen finden Sie beispielsweise in Matouseks Buch Lectures on Discrete Geometry oder in diesem Beitrag . $n$ $O(r^2)$ $1\le r\le n$ $O(n/r)$

Meine Frage ist, ob die Ebene durch -Linien (in -Regionen) unterteilt werden kann, so dass das Innere einer Region von der ursprünglichen Linien geschnitten wird . $O(r)$ $O(r^2)$ $O(n/r)$

co.combinatorics cg.comp-geom domotorp
quelle

1

Eine zufällige Stichprobe der Größe r würde den Trick machen, würde ich denken.

Suresh Venkat

3

Ich dachte, bei der Auswahl einer Stichprobe der Größe r wurde das Schnitt-Lemma ursprünglich bewiesen. Es kann jedoch ein Problem auftreten, wenn die Anordnung der abgetasteten Linien Zellen mit vielen Kanten enthält. Wenn Sie eine kanonische Triangulation der Zellen auswählen (z. B. jeden Scheitelpunkt der Zelle mit dem unteren Scheitelpunkt verbinden), wird jedes Dreieck von wenigen Linien geschnitten Dies entspricht jedoch nicht ganz der Aussage, dass die gesamte Zelle von wenigen Linien durchschnitten wird.

David Eppstein

7

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 -Linien der ursprünglichen Reihe von Linien gibt, so dass diese vertikale Zerlegung einen 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 Netz der Linien gehören. Diese Konstruktion zeigt jedoch, dass jedes Netz in 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)$ $\epsilon$

Sariel Har-Peled
quelle

1

Ich weiß nicht einmal, warum ich meine Fragen hier

poste,

1

denn dann können auch andere davon profitieren, und Sariel muss nicht mehrere E-Mails an Personen senden. :)

Suresh Venkat

1

... weil E-Mail Arbeit ist, aber das Spaß macht?

Sariel Har-Peled

7

$O(r)$ $n$ $n$ $r$ $n$

David Eppstein
quelle

Stimmt das Schnitt-Lemma mit O (r) -Linien?

Antworten: