मान लीजिए कि मेरे पास प्रत्येक किनारे से जुड़ी दूरी के साथ एक पूर्ण, अप्रत्यक्ष ग्राफ जी है। किनारे का अर्थ (यू, वी) लंबाई एल है "अंक यू और वी एल के अलावा एक दूसरे के करीब नहीं हो सकता है।" मेरा लक्ष्य एक विमान में इस ग्राफ के नोड्स को रखना है ताकि इन दूरी की बाधाओं में से कोई भी उल्लंघन न हो और इस तरह के बिंदुओं के उत्तल ढक्कन में कम से कम कुल क्षेत्र हो। उदाहरण के तौर पर, मान लीजिए कि मेरे पास विद्युत घटकों का एक गुच्छा है जिसे मैं एक चिप पर रखना चाहता हूं, जिनमें से प्रत्येक बिजली की हस्तक्षेप उत्पन्न करता है। यदि मैं घटकों को एक साथ बहुत करीब रखता हूं, तो वे एक दूसरे के साथ हस्तक्षेप करना शुरू कर देंगे, पूरे सिस्टम को बेकार कर देंगे। न्यूनतम दूरी को देखते हुए प्रत्येक बिंदु एक दूसरे बिंदु से होना चाहिए, चिप पर घटकों को रखने का सबसे अधिक अंतरिक्ष-कुशल तरीका क्या है?विमान में क्लोज-पैकिंग अंक?
मुझे नहीं पता कि इस बारे में भी सोचना शुरू करना है। मुझे यह भी नहीं पता कि समस्या उच्च-आयामी मामले (हाइपरप्लेन में पैकिंग पॉइंट्स) को सामान्यीकृत कैसे कर सकती है। क्या किसी को इस समस्या से निपटने का एक अच्छा तरीका पता है?
आप ग्राफ ड्राइंग देखना चाहते हैं। बल-निर्देशित तकनीकें आपको इस मामले के लिए एक अच्छा परिणाम दे सकती हैं। – novalis
@ novalis- मुझे इन तकनीकों से अवगत है, लेकिन मेरे सबसे अच्छे ज्ञान के लिए कोई प्रमाण नहीं है कि ये इष्टतम समाधान (या इष्टतम समाधान के करीब कुछ भी) देते हैं। मैं एक एल्गोरिदम की तलाश में हूं जो इष्टतम के कुछ अनुमानित कारक के भीतर होगा। – templatetypedef
उत्तल हॉल (प्रति क्रिस हॉपमैन के उत्तर) के क्षेत्र की बजाय, आप शायद पहलू अनुपात के उत्पाद और त्रिज्या से दूरदराज के बिंदु तक कुछ कम करना चाहते हैं। मैं यह समझने के लिए मान रहा हूं कि आपका ग्राफ पूरी तरह से घना है - आपके पास ऐसे घटक नहीं हैं जो एक ही स्थिति में 'ढेर' हो सकते हैं? – Novelocrat