मैं एक एल्गोरिदम के बारे में सोच रहा हूं जो सच या गलत लौटाता है, मुझे बता रहा है कि क्या अंक ए के सेट के चारों ओर एक सर्कल खींचना संभव है, जैसे कि बिंदु बी के सेट से कोई भी बिंदु इसके अंदर नहीं है, या दूसरी तरफ (अंक बी के एक सेट के चारों ओर एक सर्कल आकर्षित करना संभव है, जैसे अंक ए के सेट से कोई भी बिंदु इसके अंदर नहीं है)।आप कैसे निर्धारित करते हैं कि आप अंक के एक सेट के चारों ओर एक चक्र खींच सकते हैं, जैसे कि दूसरे सेट के अंक इसके अंदर नहीं हैं?
असल में, आपको इनपुट के रूप में अंक के 2 सेट दिए जाते हैं, और आपको यह निर्धारित करने की आवश्यकता है कि किसी एक के चारों ओर एक सर्कल खींचना संभव है, जैसे कि दूसरे से कोई भी बिंदु इसके अंदर नहीं है।
मैंने Megiddo's linear time algorithm पर smallest enclosing circle problem के लिए देखा है, लेकिन समस्या यह है कि यह केवल छोटे सर्कल को खींचता है, जिसका अर्थ है कि यह उस स्थिति में काम नहीं करता है जहां आपको एक बड़े सर्कल की आवश्यकता है। ,
इस तस्वीर यह लाल अंक के सेट के चारों ओर एक बहुत बड़ा वृत्त आकर्षित करने के लिए संभव है में इतना हरा अंक में से किसी एक नहीं हैं कि:
यहाँ मैं क्या मतलब है की एक तस्वीर है इसके अंदर, इसलिए मेगीद्दो का एल्गोरिदम काम नहीं करेगा।
आपके सार से: "हम यह तय करते हैं कि दो सेट गोलाकार रूप से विभाजित हैं या नहीं * ओ * (* एन *) समय में मेगीद्दो के रैखिक प्रोग्रामिंग एल्गोरिदम के माध्यम से पूरा किया जा सकता है।" ओपी का दावा है कि मेगीद्दो का एल्गोरिदम उदाहरण पर काम नहीं करता है (लेकिन शायद यह गलत वर्तनी के लिए बदला है)। – usr2564301
@ जोंगवेयर मेगीद्दो के एल्गोरिदम से पता चलता है कि 3 डी में रैखिक प्रोग्रामिंग समस्याओं को रैखिक समय में हल किया जा सकता है। मेगीद्दी भी एल्गोरिदम का उपयोग करने का एक उदाहरण प्रदान करता है जो सबसे छोटा घेरा सर्कल पाता है। यह उदाहरण ओपी चाहता है नहीं है। हालांकि, यहां पेपर एक अलग फॉर्मूलेशन दिखाता है जो वास्तव में मेगीद्दो के एल्गोरिदम को लागू करने की अनुमति देता है। (विचार एक पैराबोलॉइड को अंक पेश कर रहा है और फिर अलग विमान ढूंढ रहा है।) –