Pertanyaan Membagi bidang poin menjadi dua bagian yang sama


Diberikan pesawat 2 dimensi di mana ada n poin. Saya perlu menghasilkan persamaan garis yang membagi bidang sedemikian rupa sehingga ada n / 2 titik di satu sisi dan n / 2 poin di sisi lain. (omong-omong ini bukan pekerjaan rumahan, saya hanya mencoba memecahkan masalah)


32
2018-06-23 23:36


asal


Jawaban:


Saya telah mengasumsikan poin berbeda, jika tidak mungkin tidak ada garis seperti itu.

Jika titik berbeda, maka garis seperti itu selalu ada dan mungkin untuk menemukan menggunakan deterministik Algoritma waktu O (nlogn).

Katakanlah poinnya adalah P1, P2, ..., P2n. Asumsikan mereka tidak semuanya pada baris yang sama. Jika mereka, maka kita dapat dengan mudah membentuk garis pembelahan.

Pertama terjemahkan poin sehingga semua koordinat (x dan y) positif.

Sekarang anggaplah kita secara ajaib memiliki titik Q pada sumbu y sedemikian rupa sehingga tidak ada garis yang dibentuk oleh titik-titik tersebut (yaitu setiap garis tak terbatas Pi-Pj) melewati Q.

Sekarang karena Q tidak terletak di dalam lambung cembung poin, kita dapat dengan mudah melihat bahwa kita dapat memesan poin dengan garis berputar melewati Q. Untuk beberapa sudut rotasi, setengah poin akan terletak di satu sisi dan setengah lainnya akan terletak di sisi lain dari garis berputar ini, atau, dengan kata lain, jika kita mempertimbangkan poin yang diurutkan berdasarkan kemiringan garis Pi-Q, kita bisa memilih kemiringan antara (median) th dan (median + 1) poin th. Pemilihan ini dapat dilakukan dalam O (n) waktu oleh setiap algoritma pemilihan waktu linier tanpa perlu benar-benar menyortir poin.

Sekarang untuk memilih poin Q.

Katakanlah Q adalah (0, b).

Misalkan Q adalah collinear dengan P1 (x1, y1) dan P2 (x2, y2).

Lalu kita punya itu

(y1-b) / x1 = (y2-b) / x2 (perhatikan kami menerjemahkan poin sehingga xi> 0).

Memecahkan untuk b memberi

b = (x1y2 - y1x2) / (x1-x2)

(Perhatikan, jika x1 = x2, maka P1 dan P2 tidak dapat menjadi collinear dengan titik pada sumbu Y).

Pertimbangkan | b |.

| b | = | x1y2 - y1x2 | / | x1 -x2 |

Sekarang biarkan xmax menjadi koordinat-x dari titik paling kanan dan ymax koordinat dari paling atas.

Juga biarkan D adalah yang terkecil nol-x-koordinat perbedaan antara dua titik (ini ada, karena tidak semua xis adalah sama, karena tidak semua titik adalah collinear).

Lalu kita punya itu | b | <= xmax * ymax / D.

Jadi, pilihlah poin Q kami (0, b) agar seperti itu | b | > b_0 = xmax * ymax / D

D dapat ditemukan dalam waktu O (nlogn).

Besarnya b_0 bisa sangat besar dan kita mungkin harus berurusan dengan masalah presisi.

Tentu saja, pilihan yang lebih baik adalah memilih Q secara acak! Dengan probabilitas 1, Anda akan menemukan titik yang Anda butuhkan, sehingga membuat waktu berjalan yang diharapkan O (n).

Jika kita bisa menemukan cara untuk memilih Q dalam waktu O (n) (dengan mencari beberapa kriteria lain), maka kita dapat membuat algoritma ini berjalan dalam waktu O (n).


26
2018-06-24 02:17



  1. Buat garis acak di pesawat itu. Arahkan setiap titik ke baris tersebut a.k.a untuk setiap titik, dapatkan titik terdekat pada baris tersebut ke titik itu.

  2. Pesan titik-titik di sepanjang garis ke arah mana pun, dan pilih titik pada garis tersebut sehingga ada jumlah titik yang sama pada garis di kedua arah.

  3. Dapatkan garis tegak lurus ke baris pertama yang melewati titik itu. Baris ini akan memiliki setengah poin asli di kedua sisinya.

Ada beberapa kasus yang harus dihindari ketika melakukan ini. Yang paling penting, jika semua titik itu sendiri pada satu baris, jangan pilih garis tegak lurus yang melewatinya. Bahkan, pilihlah garis itu sendiri sehingga Anda tidak perlu khawatir tentang memproyeksikan poin. Dalam hal matematika yang sebenarnya di balik ini, proyeksi vektor akan sangat berguna.


10
2018-06-23 23:45



Ini adalah modifikasi dari Membagi bidang poin menjadi dua bagian yang sama yang memungkinkan untuk kasus dengan titik tumpang tindih (dalam hal ini, itu akan mengatakan apakah atau tidak ada jawaban).

If number of points is odd, return "impossible".

Pick a random line (two random points)
Project all points onto this line (`O(N)` operation)
    (i.e. we pretend this line is our new X'-axis, and write down the
     X'-coordinate of each point)
Perform any median-finding algorithm on the X'-coordinates
    (`O(N)` or faster-if-desired operation)
    (returns 2 medians if no overlapping points)
Return the line perpendicular to original random line that splits the medians

In rare case of overlapping points, repeat a few times (it would take
a pathological case to prevent a solution from existing).

Ini adalah O(N) tidak seperti solusi lain yang diusulkan.

Dengan asumsi solusi ada, metode di atas mungkin akan berakhir, meskipun saya tidak memiliki bukti.

Coba algoritme di atas beberapa kali kecuali Anda mendeteksi titik tumpang tindih. Jika Anda mendeteksi sejumlah besar titik tumpang tindih, Anda mungkin berada dalam perjalanan yang kasar, tetapi ada solusi brute-force yang sangat tidak efisien yang melibatkan pemeriksaan semua kemungkinan sudut:

For every "critical slope range", perform the above algorithm 
  by choosing a line with a slope within the range.
If all critical slope ranges fail, the solution is impossible.

Sudut kritis didefinisikan sebagai sudut yang mungkin bisa mengubah hasil (bayangkan solusi untuk jawaban sebelumnya, memutar seluruh set poin sampai satu atau lebih posisi poin swap dengan satu atau lebih titik lain, melintasi garis pemisah. Ada hanya banyak dari ini, dan saya pikir mereka dibatasi oleh jumlah poin, jadi Anda mungkin melihat sesuatu dalam jangkauan O(N^2)-O(N^2 log(N)) jika Anda memiliki titik tumpang tindih, untuk pendekatan brute force.


4
2018-05-10 10:47



Saya menduga bahwa cara yang baik adalah mengurutkan / mengurutkan / memesan poin (misalnya dari kiri ke kanan), dan kemudian memilih garis yang melewati (atau di antara) titik tengah [s] dalam urutan.


1
2018-06-23 23:40



Ada kasus-kasus yang jelas di mana tidak ada solusi yang mungkin. Misalnya. ketika Anda memiliki tiga tumpukan poin. Satu titik di lokasi A, Dua titik di lokasi B, dan lima titik di lokasi C.

Jika Anda mengharapkan beberapa distribusi yang layak, Anda mungkin bisa mendapatkan hasil yang baik dengan algoritma tlayton. Untuk memilih kemiringan garis awal, Anda dapat menentukan tingkat keseluruhan titik yang ditetapkan, dan memilih sudut diagonal terbesar.


1
2018-06-23 23:53



Itu median sama membagi satu set angka dengan cara yang mirip dengan apa yang Anda coba capai, dan itu dapat dihitung dalam waktu O (n) menggunakan algoritma seleksi (Langgan di Cormen et al lebih baik, jadi Anda mungkin ingin melihat ke sana sebagai gantinya). Jadi, temukan median nilai x Anda Mx (atau nilai y Anda My jika Anda mau) dan atur x = Mx (atau y = My) dan garis tersebut akan secara aksial disejajarkan dan membagi poin Anda secara seimbang.

Jika sifat masalah Anda mengharuskan tidak lebih dari satu titik terletak di garis (jika Anda memiliki jumlah ganjil poin di set Anda, setidaknya salah satu dari mereka akan berada di garis) dan Anda menemukan itulah yang terjadi (atau Anda hanya ingin waspada terhadap kemungkinan), putar semua titik Anda dengan beberapa sudut acak, θ, dan hitung median titik-titik yang diputar. Anda kemudian memutar garis median yang Anda hitung dengan -θ dan itu akan membagi poin secara merata.

Kemungkinan memilih secara acak θ sedemikian rupa sehingga masalah memanifestasikan dirinya lagi sangat kecil dengan jumlah poin yang terbatas, tetapi jika itu terjadi, coba lagi dengan θ yang berbeda.


1
2018-06-24 02:18



Saya tidak tahu betapa bergunanya ini saya telah melihat masalah serupa ...

Jika Anda sudah memiliki vektor arah (alias koefisien dimensi pesawat Anda).

Anda kemudian dapat menemukan dua titik di dalam pesawat itu, dan hanya dengan menggunakan rumus titik tengah Anda dapat menemukan titik tengah dari pesawat itu.

Kemudian menggunakan koefisien dari bidang itu dan titik tengah Anda dapat menemukan sebuah pesawat yang dari jarak yang sama dari kedua titik, menggunakan persamaan umum pesawat.

Suatu garis kemudian akan menyatakan dalam mengekspresikan satu variabel dalam hal yang lain jadi Anda akan menemukan garis dengan jarak yang sama antara kedua pesawat.

Ada beberapa metode berbeda untuk melakukan ini seperti proyeksi menggunakan persamaan jarak dari pesawat tetapi saya yakin itu akan mempersulit banyak matematika Anda.


0
2018-06-24 00:08



Untuk menambah jawaban M: metode untuk menghasilkan Q (yang tidak begitu jauh) di O(n log n).

Untuk memulainya, biarkan Q menjadi apa saja arahkan pada sumbu y yaitu. Q = (0,b) - beberapa pilihan yang bagus mungkin (0,0) atau (0, (ymaks-ymnt) / 2).

Sekarang periksa apakah ada dua poin (x1, y1), (x2, y2) collinear dengan Q. Garis antara setiap titik dan Q adalah y = mx + b; karena b adalah konstan, ini berarti dua titik adalah collinear dengan Q jika kemiringannya m adalah sama. Jadi tentukan lerengnya msaya untuk semua poin dan periksa apakah ada duplikat: (Amoritized O(n) menggunakan hash-table)

Jika semua m berbeda, kita selesai; kami menemukan Q, dan algoritma M di atas menghasilkan garis O(n) tangga.
Jika dua titik kolinear dengan Q, kita akan menggerakkan Q hanya a mungil jumlah ε, Qbaru = (0, b + ε), dan tunjukkan bahwa Qbaru tidak akan kolinear dengan dua poin lainnya.

Kriteria untuk ε, yang diturunkan di bawah ini, adalah:

ε <mminΔ* xmnt

Untuk mulai dengan, tampilan m kami seperti ini:

msaya = ysaya/ xsaya - b / xsaya

Mari temukan perbedaan minimum antara keduanya berbeda msaya dan menyebutnya mminΔ  (O(n log n)  oleh, misalnya, menyortir kemudian membandingkan perbedaan antara msaya dan saya + 1 untuk semua i)

Jika kita fudge b oleh ε, persamaan baru untuk m menjadi:

msaya baru = ysaya/ xsaya - b / xsaya - ε / xsaya
       = mSaya tua - ε / xsaya

Sejak ε> 0 dan xsaya > 0, semua m dikurangi, dan semuanya dikurangi dengan maksimum ε / xmnt. Jadi, jika

ε / xmnt <mminΔ, yaitu.
ε <mminΔ* xmnt

itu benar, lalu dua msaya yang sebelumnya tidak setara akan dijamin tetap tidak merata.


Semua yang tersisa adalah untuk menunjukkan bahwa jika m1, tua = m2, tua, lalu m1, baru = / = m2, baru. Karena keduanya msayadikurangi dengan jumlah ε / xsaya, ini sama dengan menampilkan x1 = / = x2. Jika mereka adalah sama, maka:

y1 = m1, tuax1 + b = m2, tuax2 + b = y2

Bertolak belakang dengan asumsi kami bahwa semua poin berbeda. Jadi, m1, baru = / = m2, baru, dan tidak ada dua poin yang collinear dengan Q.


0
2018-06-24 21:12



Di sini adalah bagaimana saya mendekati masalah ini (dengan asumsi bahwa n adalah genap dan TIDAK ada tiga poin yang collinear):

1) Ambil titik dengan nilai Y terkecil. Sebut saja titik P.

2) Ambil titik ini sebagai titik asal baru, sehingga semua poin lainnya akan memiliki nilai Y positif setelah transformasi ini.

3) Untuk setiap poin lainnya (ada n - 1 poin tersisa), pikirkan di bawah sistem koordinat kutub. Setiap titik lainnya dapat direpresentasikan dengan radius dan sudut. Anda bisa mengabaikan radius dan hanya fokus pada sudut.

4) Bagaimana Anda bisa menemukan garis yang membagi poin secara merata? Temukan median sudut (n - 1). Garis dari titik P ke titik dengan sudut median akan membagi titik secara merata.

Kompleksitas waktu untuk algoritma ini adalah O (n).


0
2017-08-03 13:27



Saya mengambil ide dari Moron dan andand dan terus membentuk algoritma O (n) deterministik.

Saya juga berasumsi bahwa poinnya berbeda dan n adalah genap (pikir algoritma bisa berubah sehingga n tidak merata dengan satu titik pada garis pemisah juga didukung).

Algoritme mencoba membagi titik-titik dengan garis vertikal di antara mereka. Ini hanya gagal jika titik di tengah memiliki nilai x yang sama. Dalam hal ini algoritma menentukan berapa banyak poin dengan nilai x yang sama harus berada di kiri dan situs yang lebih rendah dan dan karenanya memutar garis.

Saya akan mencoba menjelaskan dengan sebuah contoh. Mari asumsikan kita memiliki 16 poin di pesawat. Pertama kita perlu mendapatkan poin dengan nilai x terbesar ke-8 dan titik dengan nilai x terbesar ke-9. Dengan algoritme pemilihan ini dimungkinkan dalam O (n), seperti yang ditunjukkan dalam jawaban lain. Jika nilai x dari poin itu berbeda, kita selesai. Kami membuat garis vertikal antara dua titik dan yang membagi poin sama.

Masalahnya sekarang adalah jika nilai-x sama. Jadi kami memiliki 3 set poin. Itu di sisi kiri (x <xSebuah), di tengah (x = xSebuah) dan di sisi kanan (x> xSebuah). Idenya sekarang adalah menghitung poin di sisi kiri dan menghitung berapa banyak poin dari tengah perlu pergi ke sana, jadi setengah dari poin berada di sisi itu. Kita bisa mengabaikan sisi kanan di sini karena jika kita memiliki setengah dari poin di sisi kiri, setengahnya harus berada di sisi kanan.

Jadi mari kita asumsikan kita memiliki 3 poin (c = 3) di sisi kiri, 6 di tengah dan 7 di sisi kanan (Algoritme tidak tahu hitungan dari sisi tengah atau kanan, karena tidak membutuhkannya, tetapi kita juga dapat menentukannya dalam O (n)). Kita perlu 8-3 = 5 poin dari tengah untuk pergi ke sisi kiri. Poin yang sudah kita dapatkan di langkah pertama tidak berguna sekarang, karena mereka hanya ditentukan oleh nilai x dan bisa menjadi salah satu poin di tengah.

Kami menginginkan 5 poin dari tengah dengan nilai y terendah di sisi kiri dan titik dengan nilai y tertinggi di sisi kanan. Sekali lagi menggunakan algoritma seleksi, kita mendapatkan titik dengan nilai y terbesar ke-5 dan titik dengan nilai y terbesar ke-6. Kedua poin akan memiliki nilai x sama dengan xSebuah, kalau tidak kita tidak akan sampai ke langkah ini, karena akan ada garis vertikal.

Sekarang kita bisa membuat titik Q di tengah dua titik itu. Itu satu poin dari garis yang dihasilkan. Titik lain diperlukan, sehingga tidak ada poin dari sisi kiri atau kanan dibagi. Untuk mencapai titik itu, kita perlu titik dari sisi kiri, yang memiliki sudut terendah (bh) antara garis vertikal pada xSebuah  dan garis yang ditentukan oleh titik itu dan Q. Kami juga membutuhkan titik itu dari sisi kanan (dengan sudut ag). Titik R baru adalah antara titik dengan sudut yang lebih rendah dan titik pada garis vertikal (Jika sudut bawah berada di sisi kiri, titik di atas Q dan jika sudut bawah berada di sisi kanan, titik di bawah Q).

Garis yang ditentukan oleh Q dan R membagi titik di tengah sehingga ada banyak titik di kedua sisi. Itu tidak membagi poin di sisi kiri atau kanan, karena jika titik itu akan memiliki sudut yang lebih rendah dan akan dipilih untuk menghitung R.

Dari pandangan seorang matematikawan yang seharusnya bekerja dengan baik di O (n). Untuk program komputer, cukup mudah menemukan sebuah kasus di mana presisi menjadi masalah. Contoh dengan 4 poin akan A (0, 100000000), B (0, 100000001), C (0, 0), D (0,0000001, 0). Dalam contoh ini, Q adalah (0, 100000000.5) dan R (0.00000005, 0). Yang memberi B dan C di sisi kiri dan A dan D di sisi kanan. Tetapi ada kemungkinan bahwa A dan B keduanya berada di garis pembatas, karena kesalahan pembulatan. Atau mungkin hanya salah satunya. Jadi itu milik nilai input jika algoritma ini sesuai dengan persyaratan.

  1. dapatkan dua poin PSebuah(xSebuah, ySebuah) dan Pb(xb, yb)
    yang merupakan median berdasarkan nilai x > O(n)
  2. jika xSebuah ! = xb kamu bisa berhenti di sini
    karena garis paralel y-axis antara dua titik itu adalah hasilnya > O(1)
  3. dapatkan semua titik di mana nilai x sama dengan xSebuah  > O(n)
  4. hitung poin dengan nilai x kurang dari xSebuah sebagai c > O(n)
  5. dapatkan titik terendah Pc berdasarkan nilai y dari titik-titik dari 3. > O(n)
  6. dapatkan poin terbesar Pd berdasarkan nilai y dari titik-titik dari 3. > O(n)
  7. dapatkan titik terbesar (n / 2-c) Pe berdasarkan nilai y dari titik-titik dari 3. > O(n)
  8. juga mendapatkan poin P terbesar berikutnyaf berdasarkan nilai y dari titik-titik dari 3. > O(n)
  9. buat titik baru Q (xSebuah, (ye+ yf) / 2) antara Pe dan Pf  > O(1)
  10. untuk semua poin Psaya menghitung
    sudut asaya antara Pc, Q dan Psaya dan
    sudut bsaya antara Pd, Q dan Psaya  > O(n)
  11. mendapatkan poin Pg dengan sudut terendah ag (dengang> 0 ° dan ag<180 °) > O(n)
  12. mendapatkan poin Ph dengan sudut terendah bh (dengan bh> 0 ° dan bh<180 °) > O(n)
  13. jika tidak ada Pg atau Ph (semua poin memiliki nilai x yang sama)
      buat titik baru R (xSebuah+1, 0) di mana saja tetapi dengan nilai x yang berbeda dari xSebuah
    lain jika ag lebih rendah dari bh
      buat titik baru R ((xc+ xg) / 2, (yc+ yg) / 2) antara Pc dan Pg
    lain
      buat titik baru R ((xd+ xh) / 2, (yd+ yh) / 2) antara Pd dan Ph  > O(1) 
  14. garis yang ditentukan oleh Q dan R membagi poin > O(1)

0
2018-06-24 16:13