Tại sao chúng ta so sánh nhiều nhất 7 điểm trong thuật toán cặp gần nhất?

Question

Vì vậy, nếu trong vòng δ * 2δ hình chữ nhật R, chúng tôi chỉ cần so sánh một điểm từ phía bên trái với 7 điểm ở phía bên phải. Những gì tôi không hiểu là, mặc dù đọc bằng chứng, bên trong R chúng ta có thể điền vào nhiều điểm như chúng ta muốn bên trong hình chữ nhật có thể vượt quá tổng số 7. Hãy tưởng tượng nếu chúng ta có δ = 2, một điểm p (1,2, 1.1) ở phía bên trái, và ở phía bên phải, chúng tôi có một bó toàn bộ q, chẳng hạn như q (1,5, 1,7), q (1,4, 1,3), ..... làm thế nào chỉ có thể so sánh 7 điểm phát hiện cặp gần nhất? Tôi nghĩ rằng chúng ta phải so sánh mọi điểm trong hình chữ nhật R nếu đúng như vậy. Làm ơn giúp tôi.

Answer 1

Chỉ có thể có 6 điểm bên trong hình chữ nhật của bạn, vì đó là số điểm tối đa bạn có thể đặt trong hình chữ nhật với các cạnh \ delta và 2 * \ delta duy trì thuộc tính mà chúng ở ít nhất \ delta cách xa nhau khác.

Cách đặt những 6 điểm được thể hiện trong hình bên dưới:

Bạn có thể kiểm tra cho chính mình rằng có cách đặt điểm khác bên trong hình chữ nhật mà không vi phạm tài sản khoảng cách. Nếu bạn thêm nhiều hơn 6 điểm, chúng sẽ nhỏ hơn \ delta, đó là mâu thuẫn, vì \ delta được cho là khoảng cách giữa cặp gần nhất.

Vì có thể có tối đa 6 điểm, thử nghiệm 7 sẽ đảm bảo rằng bạn tìm ra giải pháp.

Tôi có hình 1 từ these UCSB slides, điều này có thể hữu ích cho bạn.