मैंने कुछ बिंदु (2 डी-निर्देशांक) दिए हैं और सबसे छोटे सर्कल को ढूंढना चाहते हैं, जिसमें इन सभी बिंदुओं को शामिल किया गया है। एल्गोरिदम को बहुत ही कुशल नहीं होना चाहिए (जबकि यह स्वाभाविक रूप से अच्छा होगा)।मुझे कुछ दिए गए बिंदुओं में न्यूनतम सर्कल कैसे मिल सकता है?
लिंक बहुत रोचक है लेकिन उल्लेखित परिणाम अद्यतित नहीं हैं। 1 9 83 से निम्रोद मेगीद्दो का एल्गोरिदम एक रैखिक-समय समाधान है लेकिन वेल्ज़ल की तरह अधिक व्यावहारिक एल्गोरिदम हैं, [यह उत्तर] देखें (http://stackoverflow.com/a/17329529/734191)। – Hbf
यह तथाकथित सबसे छोटा संलग्न गेंदों समस्या (आपके मामले में, सबसे छोटा enclosing सर्किल), उर्फ Miniball है। कई एल्गोरिदम और कार्यान्वयन इस समस्या के लिए वहाँ बाहर हैं - निम्न में से सभी रेखीय समय समाधान (यानी, n गेंदों दिए गए हैं, वे में हे (एन) बना रहेगा यदि आप पर विचार आयाम घ तय, घ = 2 आपके मामले में):
2 डी और 3 डी के लिए, Gärtner's implementation शायद सबसे तेज है।
उच्च आयामों के लिए (10,000 तक, कहते हैं), https://github.com/hbf/miniball पर एक नज़र डालें, जो गार्टनर, Kutz द्वारा एक एल्गोरिथ्म के कार्यान्वयन है, और फिशर (ध्यान दें: मैं सह लेखक में से एक हूँ)।
बहुत, बहुत उच्च आयामों के लिए, कोर-सेट (सन्निकटन) एल्गोरिदम तेजी से होंगे।
नोट: आप क्षेत्रों की सबसे छोटी संलग्न क्षेत्र गणना करने के लिए देख रहे हैं एक एल्गोरिथ्म के लिए, आप Computational Geometry Algorithms Library (CGAL) में एक सी ++ कार्यान्वयन मिल जाएगा। (आपको सभी सीजीएएल का उपयोग करने की आवश्यकता नहीं है; केवल आवश्यक शीर्षलेख और स्रोत फ़ाइलों को निकालें।)
[छोटे सर्कल जो 2 डी विमान पर दिए गए बिंदुओं को कवर करता है] का संभावित डुप्लिकेट (http://stackoverflow.com/questions/4901535/छोटी से छोटी-चक्र-जो-कवर से मिली-अंक-ऑन-2 डी विमान); एक ही उपयोगकर्ता द्वारा एक समान उत्तर है, और दूसरे प्रश्न में मेरी राय में बेहतर शब्द है। इस संस्करण में केवल एकमात्र उत्तर भी महान नहीं है ... – Benjamin