Referensi ke batas bawah pada pemisah dalam kisi?

13

Sangat mudah untuk memverifikasi bahwa dengan grid d dimensi dari titik integer , dengan kedekatan reguler, orang dapat menemukan pemisah ukuran n d - 1 (cukup pilih sembarang hyperplane tengah, dan hapus semua simpulnya). Juga tidak terlalu sulit (tapi jelas tidak langsung) untuk memverifikasi bahwa setiap pemisah harus berukuran Ω ( n d - 1 ) . Adakah yang tahu refenence untuk ini?{1,...,n}dnd-1Ω(nd-1)

Sariel Har-Peled
sumber

Jawaban:

12

Sepertinya buku "Pemisah grafik, dengan aplikasi" oleh Arnold Rosenberg dan Lenwood Heath menjawab pertanyaan Anda (lihat bagian 4.3.4.), Tetapi mungkin saja saya salah memahami notasi mereka (tolong, beri tahu saya). Lagi pula, buku ini adalah referensi yang sangat komprehensif tentang pemisah.

EDIT. Berikut ini tautan unduhan di Springer: http://www.springerlink.com/content/978-0-306-46464-5

Grigory Yaroslavtsev
sumber
Sebenarnya, ini adalah aplikasi 4.2.9 di halaman 177 buku ini. Saya tidak tahu bahwa buku ini ada ... Sekarang saya harus mendapatkannya. Terima kasih.
Sariel Har-Peled
referensi yang bagus!
Suresh Venkat