Cho một vòng tròn với N được xác định điểm và một điểm M bên ngoài vòng tròn, tìm ra thời điểm đó là gần nhất với M trong những bộ N. O (logN)

Question

http://www.glassdoor.com/Interview/Google-Interview-RVW2382108.htm

Tôi đã cố gắng để đến với một giải pháp cho vấn đề này. Nhưng tôi đã không thành công .. Có thể bất kỳ một trong những xin vui lòng cho tôi một gợi ý như thế nào để tiến hành với vấn đề này.

Tôi sẽ lấy 2 cặp hai điểm. Đó là, tôi sẽ tạo ra 2 hợp âm. Tìm ra bisector vuông góc của họ. Sử dụng những bisectors, tôi sẽ tìm ra trung tâm của vòng tròn ...

Hơn nữa, tôi sẽ đưa ra phương trình của vòng tròn. Và tìm điểm giao nhau của điểm M với đường tròn ... Đó là điểm gần nhất. Tuy nhiên, điểm đó có thể hoặc không tồn tại trong tập hợp N điểm

Cảm ơn.

Answer 1

Giả sử rằng các điểm trên chu vi của vòng tròn là "theo thứ tự" (tức là được sắp xếp theo góc về tâm của vòng tròn), bạn có thể sử dụng tìm kiếm nhị phân dựa trên góc, sẽ đạt được giới hạn O(log(n)).

1. Tính góc A từ điểm M đến giữa vòng tròn - O(1).
2. Sử dụng tìm kiếm nhị phân để tìm điểm I trên chu vi có góc lớn nhất nhỏ hơn A - O(log(n)).
3. Vì vòng tròn lồi là điểm gần nhất với M là I hoặc I+1. Tính khoảng cách cho cả hai và tối thiểu - O(1).

Answer 2

Để tìm một điểm gần nhất với M, chúng ta cần thực hiện loại bỏ nhị phân các điểm dựa trên cắt phẳng. Một chút trước khi xử lý các điểm đầu vào là cần thiết sau đó chúng ta có thể tìm thấy một điểm gần nhất với bất kỳ điểm M nào trong thời gian O (lgn).

1. Tính (nếu không muốn nói nhất định) đại diện cực điểm trong định dạng (r, θ) trong đó r là khoảng cách từ trung tâm và θ là góc từ trục x trong khoảng (-180.180].
2. Sắp xếp tất cả N điểm trong thứ tự tăng dần của góc từ trục x.

Lưu ý rằng tìm kiếm nhị phân đơn giản của một điểm gần nhất với M sẽ không làm việc ở đây, ví dụ như,

• nếu các điểm nhất định được được sắp xếp sao cho θ = (-130, -100 , -90, -23, -15,0,2,14,170), sau đó cho điểm M với θ = -170, tìm kiếm nhị phân sẽ cho -130 (40 độ) làm điểm gần nhất trong khi 170 (20 độ) là điểm gần nhất với M.
• nếu chúng ta bỏ qua dấu khi sắp xếp (nghĩ rằng nó sẽ tạo ra đầu ra chính xác), mảng được sắp xếp mới của chúng ta sẽ trông giống như θ = (0,2,14,15,23,90,100,130,170), tìm kiếm nhị phân cho một điểm M với θ = -6 sẽ cho kết quả là 2 hoặc 14 trong khi 0 là điểm gần nhất với M trong trường hợp này.

Để thực hiện các hoạt động tìm kiếm sử dụng cắt phẳng,

• Tìm dòng phẳng cắt đi qua trung tâm của vòng tròn và vuông góc với đường nối liền các trung tâm của vòng tròn với điểm M.
• Loại bỏ một nửa mặt phẳng hình tròn [90 + θ, -90 + θ) hoặc [-90 + θ, 90 + θ) tùy thuộc vào một nửa mặt phẳng M nằm.
• Thực hiện cắt phẳng song song với cắt đầu tiên và đi qua điểm ở giữa mặt phẳng trước và loại bỏ tất cả các điểm trong nửa mặt phẳng cách xa M cho đến khi không còn điểm nào trong nửa gần của mặt phẳng, trong trường hợp này loại bỏ nửa gần của mặt phẳng hơn.
• Tiếp tục cắt các mặt phẳng cho đến khi chúng ta còn lại một điểm. Điểm đó là điểm gần nhất với M. Tổng vận hành thực hiện các bước O (lgn).

Trong trường hợp dữ liệu bị sai lệch và không trải đều trong vòng tròn, chúng ta có thể tối ưu hóa cắt phẳng của chúng tôi như vậy mà mỗi lần cắt đi qua trung bình (dựa trên góc) của những điểm được trái trong hoạt động tìm kiếm.