अंक

Question

के आसपास फ़िट आयताकार को कवर करने वाले क्षेत्र को कम करने के दौरान, मैं 8 2 डी-पॉइंट्स के सेट के चारों ओर एक आयताकार फिट करने की कोशिश कर रहा हूं।

उदाहरण:

आयत में वृद्धि की और घुमाया जा सकता है। हालांकि इसे एक आयताकार रहने की जरूरत है।

मेरा पहला दृष्टिकोण प्रत्येक संभावित रोटेशन को बलपूर्वक बल देना था, जितना संभव हो सके आयत को फिट करना, और कवर किए गए क्षेत्र की गणना करना था। सबसे अच्छा फिट तब सबसे कम क्षेत्र के साथ घूर्णन होगा।

हालांकि यह वास्तव में सबसे अच्छा समाधान की तरह नहीं लगता है।

क्या ऐसा करने के लिए कोई बेहतर तरीका है?

Answer 1

पता नहीं आप "हर संभव रोटेशन की कोशिश" द्वारा क्या मतलब है, के रूप में उनमें से असीम कई हैं, लेकिन यह मूल विचार वास्तव में एक बहुत ही कुशल समाधान पैदावार:

पहला कदम की गणना करने के लिए है उत्तल पतवार। यह वास्तव में कितना बचाता है आपके डेटा के वितरण पर निर्भर करता है, लेकिन for points picked uniformly from a unit disk, the number of points on the hull is expected to be O(n^1/3)। कर रहे हैं एक number of ways to do that:

• अंक पहले से ही उनके निर्देशांक में से एक के अनुसार क्रमबद्ध रहे हैं, तो ग्राहम स्कैन एल्गोरिथ्म कि हे में (एन) करता है। दिए गए क्रम में प्रत्येक बिंदु के लिए, इसे पिछले दो में हल करें और फिर प्रत्येक अवतल बिंदु को हटा दें (केवल उम्मीदवार नए बिंदु पर पड़ोसी हैं) नए हल पर।
• यदि अंक क्रमबद्ध नहीं होते हैं, तो उपहार-रैपिंग एल्गोरिदम एक साधारण एल्गोरिदम है जो ओ (एन * एच) पर चलता है। इनपुट के बाएं बिंदु से शुरू होने वाली हल पर प्रत्येक बिंदु के लिए, प्रत्येक बिंदु को यह देखने के लिए जांचें कि यह हल पर अगला बिंदु है या नहीं। h हल पर अंक की संख्या है।
• Chen's algorithm ओ (एन लॉग एच) प्रदर्शन का वादा करता है, लेकिन मैंने काफी खोज नहीं की है कि यह कैसे काम करता है।
• _{एक और सिमल विचार अंक को उनके एजीमुथ द्वारा क्रमबद्ध करना होगा और फिर अवतल को हटा दें। हालांकि, यह केवल ओ (एन + सॉर्ट) जैसा लगता है, लेकिन मुझे डर है कि वास्तव में यह नहीं है।}

इस बिंदु पर, अब तक एकत्र पर्याप्त होना चाहिए (के रूप में दोनों मेरे और ओलिवर चार्ल्सवर्थ, और जो एव्जेनी Kluev offered a gist of a proof के लिए द्वारा conjenctured) हर कोण की जाँच। अंत में, मुझे Lior Kogan's answer में प्रासंगिक संदर्भ का संदर्भ लें।

प्रत्येक दिशा के लिए, बाउंडिंग बॉक्स को उस अंतराल में प्रत्येक कोण के लिए एक ही चार (आवश्यक रूप से अलग) बिंदुओं द्वारा परिभाषित किया जाता है। उम्मीदवारों के निर्देशों के लिए, आपके पास कम से कम एक मनमाना विकल्प होगा। इन बिंदुओं को ढूंढना एक ओ (एच^2) कार्य जैसा प्रतीत हो सकता है जब तक आपको एहसास न हो कि धुरी-गठबंधन बाध्यकारी बॉक्स के लिए चरम सीमाएं समान चरम सीमाएं हैं जिन्हें आप विलय शुरू करते हैं, और लगातार अंतराल में उनके चरम बिंदु समान या लगातार होते हैं । आइए घड़ी के क्रम में चरम बिंदु A,B,C,D पर कॉल करें, और बाउंडिंग बॉक्स को सीमित करने वाली संबंधित रेखाएं a,b,c,d हो जाएं।

तो, चलिए गणित करते हैं। बाउंडिंग बॉक्स क्षेत्र |a,c| * |b,d| द्वारा दिया गया है। लेकिन |a,c| सिर्फ वेक्टर (AC) आयत की दिशा पर प्रक्षेपित किया गया है। ua और c के समानांतर वेक्टर बनें और v लंबवत वेक्टर बनें। उन्हें सीमा में आसानी से भिन्न होने दें। वेक्टर parlance में, क्षेत्र ((AC).v)/|v| * ((BD).u)/|u| = {((AC).v) ((BD).u)}/{|u| |v|} बन जाता है। आइए हम भी u = (1,y) चुनें। फिर v = (y, -1)। यदि u ऊर्ध्वाधर है, तो इसमें सीमाओं और infinities शामिल एक मामूली समस्या है, तो चलिए बस उस मामले में क्षैतिज होने के लिए u चुनें। संख्यात्मक स्थिरता के लिए, चलिए (1,-1)..(1,1) के बाहर 90 0 हर u घुमाएं। वांछित अगर क्षेत्र को कार्टेशियन रूप में अनुवाद करना, पाठक के लिए एक अभ्यास के रूप में छोड़ दिया गया है।

Answer 2

यह दिखाया गया है अंक का एक सेट के न्यूनतम क्षेत्र आयत इस के लिए ["Determining the Minimum-Area Encasing Rectangle for an Arbitrary Closed Curve" [फ्रीमैन, शापिरा 1975]

एक ओ (nlogn) समाधान संग्रह के उत्तल पतवार बहुभुज के किनारों से एक के साथ समरेख है कि समस्या "On the computation of minimum encasing rectangles and set diameters" में प्रकाशित हुआ था [एलीसन, नोगा, 1981]

एक सरल और सुरुचिपूर्ण हे (एन) के घोल में "A Linear time algorithm for the minimum area rectangle enclosing a convex polygon" प्रकाशित किया गया था [अर्नोन, Gieselmann 1983] जब इनपुट उत्तल पतवार है (constructing a convex hull की जटिलता के बराबर है इनपुट अंक क्रमबद्ध करने की जटिलता)। समाधान Shamos, 1978 में वर्णित Rotating calipers विधि पर आधारित है। एक ऑनलाइन प्रदर्शन here उपलब्ध है।

Answer 3

पहली बात यह है कि जब मैंने यह समस्या देखी तो मुख्य घटक विश्लेषण का उपयोग करना था। मैं अनुमान लगाता हूं कि सबसे छोटा आयताकार वह है जो दो स्थितियों को पूरा करता है: किनारों को मुख्य अक्षों के साथ समानांतर होता है और कम से कम चार बिंदु किनारों (बाध्य बिंदुओं) पर होते हैं। एन आयामों के लिए एक विस्तार होना चाहिए।