Apakah pemotongan lemma benar dengan garis O (r)?

8

Lemma pemotongan (lemma penguraian sel) menyatakan bahwa diberi garis dalam bidang dimungkinkan untuk membaginya menjadi daerah (bahkan segitiga) untuk setiap sehingga interior setiap wilayah berpotongan dengan garis . Untuk lebih lanjut lihat misalnya buku Matousek's Lectures on Discrete Geometry atau posting ini . $n$ $O(r^2)$ $1\le r\le n$ $O(n/r)$

Pertanyaan saya adalah apakah pesawat dapat dibagi dengan garis (menjadi daerah ) sehingga interior suatu daerah berpotongan oleh dari garis aslinya. $O(r)$ $O(r^2)$ $O(n/r)$

co.combinatorics cg.comp-geom domotorp
sumber

1

Sampel acak ukuran r akan melakukan trik, saya pikir.

Suresh Venkat

3

Saya pikir memilih sampel ukuran r adalah bagaimana lemma pemotongan pada awalnya terbukti. Tetapi mungkin ada masalah ketika susunan garis sampel memiliki sel dengan banyak ujung - jika Anda memilih triangulasi kanonik sel (mis. Hubungkan setiap simpul sel ke simpul bawah) maka setiap segitiga akan berpotongan dengan beberapa garis tapi itu tidak persis sama dengan pernyataan bahwa seluruh sel berpotongan oleh beberapa baris.

David Eppstein

7

Jadi, anggap Anda membuat Anda dekomposisi vertikal dengan mengambil garis , mengambil pengaturannya, dan kemudian menghitung dekomposisi vertikalnya. Pertanyaannya adalah apakah ada himpunan garis dari himpunan garis semula sehingga dekomposisi vertikal ini membentuk potongan . $O(r)$ $O(r)$ $1/r$

Sekarang, jika Anda mengambil konstruksi Noga Alon dalam makalah ini:

www.math.tau.ac.il/~nogaa/PDFS/epsnet3.pdf

dan memodifikasinya, Anda mendapatkan satu set garis, sehingga jika suatu titik terkandung dalam lebih dari garis , dari salah satu garis harus milik -net garis. Namun konstruksi ini menunjukkan bahwa jaring apa pun, harus berukuran sangat super linier dalam . Hasil Noga juga berlaku untuk orang yang lemah versi -net. Yang menunjukkan bahwa tidak ada set garis apa pun yang akan memiliki properti yang diinginkan. $n/r$ $1/r$ $O(r)$ $\epsilon$

Sariel Har-Peled
sumber

1

Saya bahkan tidak tahu mengapa saya mengirim pertanyaan saya di sini, bukan hanya mengirim email kepada Anda ...

domotorp

1

karena dengan begitu orang lain juga mendapat manfaat, dan Sariel tidak perlu mengirim banyak email ke orang. :)

Suresh Venkat

1

... karena email itu berfungsi, tetapi ini menyenangkan?

Sariel Har-Peled

7

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

David Eppstein
sumber

Apakah pemotongan lemma benar dengan garis O (r)?

Jawaban: