2 डी विमान

Question

समस्या पर दिए गए बिंदुओं को कवर करने वाला सबसे छोटा सर्कल समस्या: एक सर्कल का सबसे छोटा संभव व्यास क्या है जो 2 डी विमान पर एन अंक दिए गए हैं?

इस समस्या को हल करने के लिए सबसे कुशल एल्गोरिदम क्या है और यह कैसे काम करता है?

Answer 1

यह smallest circle problem है। सुझाए गए एल्गोरिदम के लिंक के संदर्भ देखें।

E.Welzl, सबसे छोटा enclosing डिस्क (बॉल्स और ellipsoids), एच में Maurer (सं।), न्यू परिणाम और नई प्रवृत्तियां कंप्यूटर विज्ञान में, कंप्यूटर विज्ञान में व्याख्यान नोट्स, वॉल्यूम। 555, स्प्रिंगर-वर्लग, 359-37 (1991)

"सबसे तेज" एल्गोरिथ्म के संदर्भ में है।

Answer 2

के लिए वहां कई एल्गोरिदम और कार्यान्वयन हैं जो सबसे छोटी गेंदों समस्या के लिए हैं।

• 2 डी और 3 डी, Gärtner's implementation शायद सबसे तेज़ है।

• उच्च आयामों के लिए (10,000 तक, कहते हैं), https://github.com/hbf/miniball पर एक नज़र डालें, जो गार्टनर, Kutz द्वारा एक एल्गोरिथ्म के कार्यान्वयन है, और फिशर (ध्यान दें: मैं सह लेखक में से एक हूँ)।

• बहुत, बहुत उच्च आयामों के लिए, कोर-सेट (सन्निकटन) एल्गोरिदम तेजी से होंगे।

नोट: आप क्षेत्रों की सबसे छोटी संलग्न क्षेत्र गणना करने के लिए देख रहे हैं एक एल्गोरिथ्म के लिए, आप Computational Geometry Algorithms Library (CGAL) में एक सी ++ कार्यान्वयन मिल जाएगा।

http://www.dma.fi.upm.es/mabellanas/tfcs/fvd/algorithm.html 

पता चला है 2 घ समस्या के लिए वास्तव में अच्छी तरह से काम करने के लिए

Answer 3

दूर बिंदु voronoi आरेख दृष्टिकोण, (बस आवश्यक हेडर और स्रोत फ़ाइलों को अलग आप CGAL के सभी उपयोग करने की आवश्यकता नहीं है।)। यह गैर-पुनरावर्तक है और (निश्चित रूप से) गारंटीकृत सटीक है। मुझे संदेह है कि यह उच्च आयामों तक इतना अच्छा नहीं बढ़ता है, यही कारण है कि साहित्य में इसका कोई ध्यान नहीं है।

यदि रुचि है तो मैं इसका वर्णन यहां करूंगा - उपर्युक्त लिंक मुझे लगता है कि मुझे लगता है कि थोड़ा मुश्किल है।

संपादित एक और लिंक: http://ojs.statsbiblioteket.dk/index.php/daimipb/article/view/6704