Apakah triangulasi Delaunay pada bola memaksimalkan sudut minimum?

Delaunay triangulasi dalam pesawat memaksimalkan sudut minimum dalam segitiga. Apakah hal yang sama berlaku untuk triangulasi poin Delaunay pada bola? (di sini "sudut" adalah sudut lokal di lingkungan sekitar titik di puncak).

Terinspirasi oleh tetapi tidak terkait dengan pertanyaan ini di Math.SE.

cg.comp-geom delaunay-triangulation Suresh Venkat
sumber

Tentu saja properti itu akan berlaku untuk satu set yang dilokalisasi ke wilayah bola yang kecil dan datar, karena itu bermacam-macam. Pertanyaan sebenarnya adalah apakah properti itu dikorbankan ketika poin tersebar di bola. Dugaan saya adalah bahwa untuk memiliki triangulasi Delaunay di tempat pertama, Anda akan membutuhkan segitiga lemak lebih banyak daripada dalam kasus Euclidean, sehingga properti akan tahan.

Josephine Moeller

Tidakkah ini mengikuti kemudian dari fakta bahwa proyeksi stereografik dari titik generik pada bola memetakan lingkaran ke lingkaran dan mempertahankan sudut antara kurva berpotongan (~ tepi) karena kesesuaian? Atau apakah saya melewatkan sesuatu?

seseorang

@ seseorang Yep, itu harus melakukannya. Setidaknya sebagian besar. Mungkin ada satu atau dua halangan, tetapi itu akan menjadi ide sentral. Saya bertanya-tanya tentang itu. Saya tidak menyadari bahwa pemetaan stereografis itu sesuai.

Josephine Moeller

@ SureshVenkat Sekarang Anda menyebutkan ruang hiperbolik, mungkin saya memiliki intuisi saya ke belakang. Dalam ruang hiperbolik Anda harus memperhitungkan fakta bahwa ada lingkaran "ilegal" (yaitu hypercycles dan horocycles). Sementara di ruang bola Anda tidak; Anda selalu dapat menemukan lingkaran yang melewati tiga titik.

Josephine Moeller

Saya pikir ini tidak berhasil. Anda ingin memastikan proyeksi mengambil lingkaran besar ke garis-garis (karena Anda mengukur sudut antara tepi segitiga, yang merupakan lingkaran besar / lurus). Saya tidak berpikir Anda tidak dapat melakukan ini dengan proyeksi stereografi. Anda hanya dapat melakukan ini dengan proyeksi dari titik di pusat bola, yang membawa beberapa lingkaran ke elips.

Peter Shor

Jawaban:

ARGUMEN PERTAMA: Ini adalah jawaban pertama saya. Perhatikan bahwa argumen ini salah. Lihat argumen kedua saya di bawah ini.

Saya pikir itu tidak benar. Alasannya ia bekerja di dalam pesawat adalah bahwa dalam sebuah lingkaran, sudut tulisan yang digantikan oleh akor adalah setengah dari sudut tengah yang sesuai. Jadi, jika kita memiliki segitiga dengan sudut kecil, setiap titik yang akan membuat sudut lebih besar dengan tepi yang berlawanan berada di dalam lingkaran Delaunay yang kosong, dan karena itu bukan salah satu titik dalam konfigurasi yang kami temukan triangulasi.

Sekarang, anggaplah Anda memiliki triangulasi Delaunay di bola. Tempatkan titik di tengah bola, dan proyeksikan semua pion ke dalam pesawat. Tepi segitiga (lingkaran besar di bola) semuanya dibawa ke segmen garis. Tetapi lingkaran yang memberikan properti bola kosong dibawa ke elips, dan jika ada titik di luar elips yang diproyeksikan tetapi di dalam lingkaran segitiga, titik ini akan membuat sudut yang lebih besar dengan tepi.

EDIT:

Tunggu sebentar. Jawaban ini sepenuhnya salah, karena proyeksi pusat tidak mempertahankan sudut. Saya masih berpikir dugaan itu salah, karena saya punya argumen yang jauh lebih rumit bahwa teorema tentang sudut yang tertulis tidak berlaku pada bola. Inilah argumennya:

ARGUMEN KEDUA:

Alasan ini berlaku di pesawat adalah bahwa sudut yang dituliskan digantikan oleh akord adalah setengah dari sudut tengah yang sesuai. Itu berlaku karena, dalam diagram di bawah ini, kita memiliki dan

C Y X_{2} = \frac{1}{2} (π - X_{2} C Y)

$CYX_2 = \frac{1}{2} (\pi - X_2 C Y)$

Mengurangkan, kita mendapatkan

C Y X_{1} = \frac{1}{2} (π - X_{1} C Y) .

$C Y X_1 = \frac{1}{2} (\pi - X_1 C Y).$

X_{1} Y X_{2} = \frac{1}{2} X_{1} C X_{2} .

$X_1 Y X_2 = \frac{1}{2} X_1 C X_2.$

gambar geometri

C Y X_{2} = \frac{1}{2} (π - X_{2} C Y + SEBUAH (X_{2} C Y))

$CYX_2 = \frac{1}{2} ( \pi - X_2CY + A(X_2CY) \,)$

C Y X_{1} = \frac{1}{2} (π - X_{1} C Y + SEBUAH (X_{1} C Y)),

$CYX_1 = \frac{1}{2} ( \pi - X_1CY + A(X_1CY) \,),$

A (X Y Z)

$A(XYZ)$

X_{1} Y X_{2} = \frac{1}{2} (X_{1} C X_{2} + SEBUAH (X_{2} C Y) - SEBUAH (X_{1} C Y)) .

$X_1 Y X_2 = \frac{1}{2} (X_1 C X_2 + A(X_2CY) - A(X_1CY)\,).$

$Y$ $X_1YX_2$ $A(X_2CY) - A(X_1CY)$ $X_1X_2$ $A(XCY)$ $0$ $X$ $Y$ $X=Y$

$Y$ $X_1YX_2$ $X_1YX_2$ $Y'$ $X_1YX_2$ $X_1YX_2 < X_1 Y' X_2$

Peter Shor
sumber

Saya tidak berharap pertanyaan ini menjadi begitu rumit :). bersemangat menunggu gambar.

Suresh Venkat