Fréchet distance
गणित में, फ्रेचेट दूरी वक्रों के बीच समानता का एक उपाय है जो वक्रों के साथ बिंदुओं के स्थान और क्रम को ध्यान में रखता है। इसका नाम मौरिस फ्रेचेट के नाम पर रखा गया है। सहज परिभाषा कल्पना कीजिए कि एक व्यक्ति अपने कुत्ते को एक पट्टी पर चलते हुए एक सीमित घुमावदार रास्ते को पार कर रहा है, जिसमें कुत्ता एक अलग सीमित घुमावदार रास्ते को पार कर रहा है। प्रत्येक पट्टा को सुस्त रखने के लिए अपनी गति बदल सकता है, लेकिन दोनों में से कोई भी पीछे की ओर नहीं बढ़ सकता है। दो वक्रों के बीच फ्रेचेट दूरी सबसे छोटी पट्टी की लंबाई है जो दोनों के लिए शुरू से अंत तक अपने अलग-अलग रास्तों को पार करने के लिए पर्याप्त है। ध्यान दें कि परिभाषा दो वक्रों के संबंध में सममित है-फ्रेचेट दूरी समान होगी यदि कुत्ता अपने मालिक को चला रहा था। औपचारिक परिभाषा मान लीजिए कि एक मीट्रिक स्थान है। एक वक्र इकाई अंतराल से एक निरंतर मानचित्र है, अर्थात। रीपैरामेटेराइजेशन एक निरंतर, गैर-घटता, अधिगमन है। दो दिए गए वक्र होने दें। फिर, और के बीच की फ्रेचेट दूरी को सभी पुनर्निर्धारणों पर अधिकतम और और के बीच की सभी दूरी पर अधिकतम के रूप में परिभाषित किया जाता है। गणितीय संकेतन में, फ्रेचेट दूरी है जहाँ का दूरी फलन है। अनौपचारिक रूप से, हम पैरामीटर को "समय" के रूप में सोच सकते हैं। फिर, कुत्ते की स्थिति है और समय पर कुत्ते के मालिक की स्थिति है (या इसके विपरीत)। समय पर उनके बीच पट्टा की लंबाई और के बीच की दूरी है। के सभी संभावित पुनर्परिमाणों पर अधिकतम लेना दिए गए रास्तों के साथ चलने का चयन करने के अनुरूप है जहां अधिकतम पट्टा की लंबाई कम से कम है। प्रतिबंध और गैर-घटाने का मतलब है कि न तो कुत्ता और न ही उसका मालिक पीछे हट सकता है। फ्रेचेट मीट्रिक दो वक्रों के प्रवाह को ध्यान में रखता है क्योंकि उन बिंदुओं के जोड़े जिनकी दूरी उनके संबंधित वक्रों के साथ लगातार फ्रेचेट दूरी में योगदान देती है। यह फ्रेचेट दूरी को वक्रों के लिए विकल्पों की तुलना में समानता का एक बेहतर उपाय बनाता है, जैसे कि हौसडॉर्फ दूरी, मनमाने बिंदु सेटों के लिए। यह संभव है कि दो वक्रों में छोटी हौसडॉर्फ दूरी हो लेकिन बड़ी फ्रेचेट दूरी हो। फ्रेचेट दूरी और इसके रूप कई समस्याओं में अनुप्रयोग पाते हैं, मॉर्फिंग और हस्तलेखन पहचान से लेकर प्रोटीन संरचना संरेखण तक। ऑल्ट और गोडाउ पैरामीट्रिक खोज के सिद्धांत के आधार पर यूक्लिडियन स्पेस में दो बहुभुज वक्रों के बीच फ्रेचेट दूरी की गणना करने के लिए एक बहुपद-समय एल्गोरिथ्म का वर्णन करने वाले पहले व्यक्ति थे। उनके एल्गोरिथ्म का चलने का समय m और n खंडों के साथ दो बहुभुज वक्रों के लिए है। फ्री-स्पेस आरेख दो वक्रों की फ्रेचेट दूरी की गणना करने के लिए एक महत्वपूर्ण उपकरण फ्री-स्पेस आरेख है, जिसे ऑल्ट और गोडाउ द्वारा पेश किया गया था। दी गई दूरी की सीमा ε के लिए दो वक्रों के बीच मुक्त-स्थान आरेख पैरामीटर स्थान में एक द्वि-आयामी क्षेत्र है जिसमें दो वक्रों पर सभी बिंदु जोड़े अधिकतम ε दूरी पर होते हैंः फ्रेचेट दूरी अधिकतम ε पर होती है यदि और केवल तभी जब मुक्त-स्थान आरेख में निचले बाएँ कोने से ऊपरी दाएँ कोने तक का मार्ग होता है, जो क्षैतिज और ऊर्ध्वाधर दोनों दिशाओं में मोनोटोन होता है। संभाव्यता वितरण (एफ. आई. डी. स्कोर) के बीच की दूरी के रूप में वक्रों के बीच की दूरी को मापने के अलावा, फ्रेचेट दूरी का उपयोग संभाव्यता वितरण के बीच के अंतर को मापने के लिए भी किया जा सकता है। दो बहुभिन्नरूपी गौसी वितरणों के लिए साधन और सहप्रसरण मैट्रिक्स के साथ और इन वितरणों के बीच फ्रेचेट दूरी है। यह दूरी फ्रेचेट स्थापना दूरी (एफ. आई. डी.) का आधार है जिसका उपयोग एक उत्पादक प्रतिकूल नेटवर्क द्वारा उत्पादित छवियों की तुलना प्रशिक्षण के लिए उपयोग की जाने वाली वास्तविक छवियों से करने के लिए किया जाता है। प्रकार कमजोर फ्रेचेट दूरी शास्त्रीय फ्रेचेट दूरी का एक प्रकार है, इस आवश्यकता के बिना कि अंतिम बिंदु अपने-अपने वक्रों के साथ नीरस रूप से आगे बढ़ें-कुत्ते और उसके मालिक को उनके बीच की पट्टी को छोटा रखने के लिए पीछे हटने की अनुमति है। ऑल्ट और गोडाउ एक संबंधित ग्रिड ग्राफ में मिनीमैक्स पथों की गणना के आधार पर बहुभुज वक्रों के बीच कमजोर फ्रेचेट दूरी की गणना करने के लिए एक सरल एल्गोरिथ्म का वर्णन करते हैं। असतत फ्रेचेट दूरी, जिसे युग्मन दूरी भी कहा जाता है, बहुभुज वक्रों के लिए फ्रेचेट मीट्रिक का एक अनुमान है, जिसे ईटर और मनीला द्वारा परिभाषित किया गया है। असतत फ्रेचेट दूरी पट्टी की केवल उन स्थितियों पर विचार करती है जहाँ इसके अंतिम बिंदु दो बहुभुज वक्रों के शीर्षों पर स्थित होते हैं और कभी भी किनारे के आंतरिक भाग में नहीं होते हैं। यह विशेष संरचना एक आसान गतिशील प्रोग्रामिंग एल्गोरिथ्म द्वारा बहुपद समय में असतत फ्रेचेट दूरी की गणना करने की अनुमति देती है। जब दो वक्रों को यूक्लिडियन स्थान के अलावा एक मीट्रिक स्थान में एम्बेड किया जाता है, जैसे कि एक पॉलीहेड्रल क्षेत्र या बाधाओं के साथ कुछ यूक्लिडियन स्थान, तो वक्रों पर दो बिंदुओं के बीच की दूरी को सबसे स्वाभाविक रूप से उनके बीच के सबसे छोटे मार्ग की लंबाई के रूप में परिभाषित किया जाता है। पट्टा को अपने अंतिम बिंदुओं से जुड़ने वाला एक भूगणितीय होना आवश्यक है। वक्रों के बीच परिणामी मीट्रिक को जियोडेसिक फ्रेचेट दूरी कहा जाता है। कुक और वेन्क एक सरल बहुभुज में दो बहुभुज वक्रों के बीच भूगणितीय फ्रेचेट दूरी की गणना करने के लिए एक बहुपद-समय एल्गोरिथ्म का वर्णन करते हैं। यदि हमें आगे यह आवश्यकता है कि पट्टा को परिवेशी मीट्रिक स्थान में लगातार चलना चाहिए, तो हम दो वक्रों के बीच समस्थानिक फ्रेचेट दूरी की धारणा प्राप्त करते हैं। पट्टा एक स्थान से दूसरे स्थान पर निरंतर रूप से नहीं जा सकता है-विशेष रूप से, पट्टा बाधाओं को पार नहीं कर सकता है, और एक इलाके में पहाड़ पर केवल तभी झाड़ सकता है जब यह काफी लंबा हो। पट्टा की गति दो वक्रों के बीच एक समस्थानिक का वर्णन करती है। चैंबर्स एट अल। यूक्लिडियन तल में बाधाओं के साथ बहुभुज वक्रों के बीच समस्थानिक फ्रेचेट दूरी की गणना करने के लिए एक बहुपद-समय एल्गोरिथ्म का वर्णन करें। उदाहरण त्रिज्या और क्रमशः दो संकेंद्रित वृत्तों के बीच फ्रेचेट दूरी सबसे लंबी पट्टी की आवश्यकता होती है जब मालिक स्थिर खड़ा होता है और कुत्ता वृत्त () के विपरीत दिशा में यात्रा करता है, और सबसे छोटी पट्टी तब होती है जब मालिक और कुत्ता दोनों वृत्त () के चारों ओर एक स्थिर कोणीय वेग से चलते हैं। अनुप्रयोग फ्रेचेट दूरी का उपयोग दृश्य पदानुक्रम, एक ग्राफिक डिजाइन सिद्धांत का अध्ययन करने के लिए किया गया है। फ्रेचेट की स्थापना की दूरी फ्रेचेट का अर्थ संदर्भ आगे पढ़ना भी देखें। .. .. मीट्रिक ज्यामिति दूरी टोपोलॉजी ज्यामितीय एल्गोरिदम