Tôi đã triển khai thành công cách tạo sơ đồ Voronoi theo 2 chiều bằng phương pháp của Fortune. Nhưng bây giờ tôi đang cố gắng sử dụng nó cho các truy vấn lân cận gần nhất cho một điểm (đó không phải là một trong những điểm ban đầu được sử dụng để tạo biểu đồ). Tôi tiếp tục thấy mọi người nói rằng nó có thể được thực hiện trong thời gian O (lg n) (và tôi tin họ), nhưng tôi không thể tìm thấy một mô tả về cách nó thực sự được thực hiện.Hàng xóm gần nhất Tìm kiếm bằng cách sử dụng Biểu đồ Voronoi
Tôi quen thuộc với tìm kiếm nhị phân, nhưng tôi không thể tìm ra một tiêu chí tốt để đảm bảo rằng giới hạn trên. Tôi cũng nghĩ rằng có lẽ nó có thể phải làm với chèn điểm vào biểu đồ và cập nhật các tế bào xung quanh, nhưng không thể nghĩ (hoặc tìm) một cách tốt để làm điều đó.
Mọi người có thể đầu mối cho tôi hoặc trỏ đến địa điểm có mô tả kỹ lưỡng hơn không?
Điều đó có ý nghĩa. Tôi nghĩ tôi quen thuộc với phương pháp đó. Tôi sẽ upvote bạn, nhưng tôi chưa thể. –
@Chad: Tôi chưa quen với cấu trúc Kirkpatrick cho đến khi tôi tìm kiếm vì câu hỏi của bạn :-) Tôi đã làm việc với sơ đồ Voronoi trước đây, nhưng tôi chưa bao giờ sử dụng chúng cho vị trí điểm. Phương pháp này trông khá đẹp. – Ante