2 डी अंतरिक्ष पी, में अंक का एक सेट को देखते हुए जहां पाई = (क्सी, यी),एक बिंदु मिल ऐसे अंक पी का एक सेट में किसी भी बिंदु को अधिकतम दूरी कम से कम है कि
मैं खोजने की जरूरत है एक लक्ष्य बिंदु टी जैसे कि किसी भी पीआई की अधिकतम दूरी कम हो जाती है।
टी पी में मौजूद करने की जरूरत नहीं है, और मनमाने ढंग से परिभाषित किया जा सकता
वहाँ एक एल्गोरिथ्म मैं इस के लिए उपयोग कर सकते हैं है?
यह smallest circle problem है।
हाँ, यह मूल रूप से मैं चाहता हूं, सिवाय इसके कि मुझे त्रिज्या की आवश्यकता नहीं है, मुझे बस केंद्र बिंदु की आवश्यकता है। – jdeuce
विकिपीडिया आलेख में इस समस्या को हल करने के लिए एक रैखिक समय एल्गोरिदम शामिल है। मुझे अत्यधिक संदेह है कि आउटपुट में त्रिज्या की आवश्यकता नहीं होने से तेज समाधान की अनुमति मिल जाएगी। –
हाँ, कागज को पढ़ने के लिए मुश्किल है हालांकि, आपको alg के लिए कोई छद्म कोड मिला है? – jdeuce
http://www.cs.mcgill.ca/~cs507/projects/1998/jacob/problem.html
सोचते हैं कि ऐसा बहुत अच्छी व्याख्या के साथ अपनी समस्या का समाधान हो सकता है, लेकिन यह हे है (एन^2)
समस्या यह है कि वास्तविक एल्गोरिदम का लिंक टूटा हुआ है। लेकिन एल्गोरिदम का प्रतिनिधित्व करने के लिए एक शांत लाइव ग्राफ। – Paparazzi
मैं इसे साबित नहीं किया है, लेकिन मुझे लगता है कि समाधान सिर्फ है:
(न्यूनतम (क्सी) + अधिकतम (क्सी))/2, (न्यूनतम (यी) + अधिकतम (यी))/2)
वास्तव में यह एक अनुमान है। छोटे सर्कल के चारों ओर एक वर्ग की कल्पना करें, अधिकतम राशि अनुमानित हो सकती है, वर्ग के कोने से सर्कल तक दूरी है। – jdeuce
किसी भी या योग एक ही बिंदु नहीं होगा। – Paparazzi
यह गैर-इष्टतम क्यों है? –
मैंने उपयोग किए गए अनुमानित समाधान के संदर्भ से छुटकारा पाने के लिए प्रश्न को अद्यतन किया, क्योंकि यह चर्चा के लिए अप्रासंगिक है। – jdeuce