Menguji apakah satu set n poin dalam bidang membentuk cembung n poligon dalam waktu (nlogn)

Asumsikan bahwa Anda diberi satu set n poin di pesawat dan Anda ingin memeriksa apakah mereka membentuk cembung n poligon, yaitu, jika mereka semua berbaring di cembung lambung. Saya bertanya-tanya apakah ada yang tahu bagaimana melakukan ini dalam waktu (nlogn), yaitu, tanpa menghitung CH.

cg.comp-geom Babis Tsourakakis
sumber

Anda dapat menghitung convex hull dalam waktu O (n log n). Apakah maksud Anda jika mungkin untuk melakukannya dalam waktu kurang dari itu?

Per Vognsen

ya, saya percaya bahwa harus ada beberapa algoritma waktu linear untuk masalah ini. tetapi saya tidak tahu caranya

Babis Tsourakakis

Dia menulis o (nlogn) bukan O (nlogn), jadi pertanyaannya benar.

Shiva Kintali

Saya menggunakan notasi kecil sehingga pertanyaannya tetap seperti

Babis Tsourakakis

Itu membuat saya sedikit berkerut melihat penyortiran angka (atau cembung ekuivalen poin Cartesian) yang dinyatakan sebagai waktu Θ (n log n) tanpa pernyataan eksplisit tentang model perhitungan apa yang Anda gunakan. Pengurutan perbandingan membutuhkan Θ (n log n) waktu tetapi model perbandingan bahkan tidak memungkinkan lambung dihitung sama sekali. Keduanya masih Θ (n log n) waktu untuk pohon keputusan aljabar (seperti yang ditunjukkan jawaban yang diterima), tetapi lebih cepat dalam model perhitungan yang lebih mirip komputer yang sebenarnya.

David Eppstein

Jawaban:

Itu tampaknya tidak mungkin, setidaknya dalam model pohon perbandingan / aljabar. Definisi pertama:

Sebuah set point berada di posisi cembung jika tidak ada titik dapat ditulis sebagai kombinasi cembung poin yang tersisa dari . $P$ $P$ $P$

Sekarang, memutuskan apakah satu set angka semuanya berbeda membutuhkan waktu (ini dikenal sebagai UNIQUENESS). Dengan seperangkat angka , petakan ke set poin Jika tidak ada angka yang diulang, maka titik-titik tersebut berada pada posisi cembung. $n$ $\Omega(n \log n)$ $n$ $X$

P = {(x, x^{2}) | x \in X} .

$P = \{ (x, x^2) | x \in X\}.$

Jika ada nomor yang diulang, maka angka yang diulang ini sesuai dengan titik yang dapat ditulis sebagai kombinasi cembung dari poin yang tersisa. Yakni, titik-titik tersebut tidak dalam posisi cembung.

Yaitu, memutuskan apakah suatu set titik berada dalam posisi cembung sama sulitnya dengan KEUNIKAN.

Sariel Har-Peled
sumber

X [i]

$X[i]$

(X [i], X [i]^{2} + i / n^{2})

$(X[i], X[i]^2+i/n^2)$

@Babis: Pengurangan Jeff berfungsi saat duplikat poin tidak diizinkan. Poin yang dihasilkan oleh reduksi adalah unik, apa pun larik awalnya.

Vinayak Pathak

Dengan demikian kita mendapatkan bahwa jumlah sudut lambung cembung sama dengan n jika dan hanya jika tidak ada dua titik memiliki koordinat x yang sama. Terima kasih banyak, awalnya saya pikir itu harus lebih mudah daripada menyortir.

Babis Tsourakakis

Terima kasih Vinayak, saya belum melihat pengurangan Jeff sejak diposting pada saat yang sama ketika saya menulis komentar sebelumnya yang saya gantikan dengan yang di atas

Babis Tsourakakis

Suresh, saya tidak setuju dengan ungkapan "model standar". Itulah yang dimaksud dengan RAM Word :) Ini adalah model yang paling cocok dengan komputer asli dan yang kami gunakan untuk menganalisis algoritma di sebagian besar TCS. Geometri telah meminta pengecualian untuk menggunakan RAM Nyata sehingga kita tidak perlu berurusan dengan masalah presisi. Tapi itu bukan "model standar."

Mihai

-1

$O(n log n)$

Setelah Anda mengetahui urutan titik, sudut dari setiap titik ke titik berikutnya dalam urutan harus monoton. Ini membentuk kondisi yang diperlukan dan, saya pikir, kondisi yang memadai.

Mendapatkan titik interior dibiarkan sebagai latihan untuk pembaca.

$O(n log n)$

BCS
sumber

Anda mungkin salah membaca o (n log n) sebagai O (n log n) seperti saya. Bagaimanapun, algoritma yang Anda gambarkan adalah pembungkus kado dalam bentuk embrionik. Anda sebenarnya tidak perlu menggunakan titik interior; Anda dapat menggunakan titik pada batas, misalnya titik dengan koordinat x minimal.

Per Vognsen

O (n l o g n)

$O(n log n)$

o ()

$o()$

Intinya adalah bahwa ada banyak algoritma cembung cembung yang berjalan di O (n log n). Algoritma Anda pada dasarnya adalah pembungkus kado kuno. Dia meminta sesuatu yang lebih cepat, misalnya waktu linier. Lihat tanggapan lain.

Per Vognsen

Mengenai hasil edit Anda, jika Anda bisa melihat jawaban yang diterima di atas milik Anda, Anda akan melihat bahwa masalahnya setara dengan keunikan elemen, yang memiliki batas bawah O (n log n).

Per Vognsen

@BCS: Saya khawatir Anda salah paham tentang jawaban Sariel Har-Peled. Pengurangannya adalah dari keunikan ke pengujian posisi cembung, bukan ke arah lain. Yaitu, Sariel (dan JeffE) menyatakan bahwa jika Anda diberi satu set angka dan ingin menguji keunikan, Anda dapat mengonversinya menjadi seperangkat poin dan menggunakan algoritma apa pun untuk pengujian posisi cembung.

Tsuyoshi Ito