Cho một tập hợp các điểm trong 2d-không gian P, trong đó Pi = (Xi, Yi),tìm một điểm sao cho khoảng cách tối đa đến bất kỳ điểm nào trong một tập hợp điểm P được giảm thiểu
Tôi cần tìm một điểm mục tiêu T sao cho khoảng cách tối đa tới bất kỳ Pi nào được giảm thiểu.
T không cần tồn tại trong P và có thể được xác định tùy ý
Có một thuật toán tôi có thể sử dụng cho điều này không?
Đây là smallest circle problem.
vâng, đây là cơ bản những gì tôi muốn, ngoại trừ tôi không cần bán kính Tôi chỉ cần điểm trung tâm. – jdeuce
Bài viết wikipedia chứa thuật toán thời gian tuyến tính để giải quyết vấn đề này. Tôi rất nghi ngờ rằng không yêu cầu bán kính trong đầu ra sẽ cho phép các giải pháp nhanh hơn. –
vâng, giấy khó đọc, bạn có bất kỳ mã giả cho alg không? – jdeuce
http://www.cs.mcgill.ca/~cs507/projects/1998/jacob/problem.html
suy nghĩ này có thể là một giải pháp cho vấn đề của bạn với lời giải thích khá tốt, nhưng nó là O (n^2)
Vấn đề là liên kết đến thuật toán thực tế bị hỏng. Nhưng một biểu đồ sống thú vị để đại diện cho thuật toán. – Paparazzi
tôi đã không chứng minh điều đó, nhưng tôi nghĩ rằng giải pháp chỉ là:
(min (Xi) + max (Xi))/2, (min (Yi) + max (Yi))/2)
thực sự đây là một xấp xỉ. tưởng tượng một hình vuông xung quanh vòng tròn nhỏ nhất, số tiền tối đa mà xấp xỉ có thể được tính ra, là khoảng cách từ góc của hình vuông đến hình tròn. – jdeuce
Bất kỳ hoặc tổng số nào sẽ không giống nhau. – Paparazzi
Tại sao nó không tối ưu? –
Tôi đã cập nhật câu hỏi để loại bỏ tham chiếu đến giải pháp gần đúng mà tôi đã sử dụng, vì nó không liên quan đến cuộc thảo luận. – jdeuce