Fréchet distance
ગણિતમાં, ફ્રેચેટ અંતર એ વણાંકો વચ્ચેની સમાનતાનું માપ છે જે વણાંકો સાથેના બિંદુઓના સ્થાન અને ક્રમને ધ્યાનમાં લે છે. તેનું નામ મૌરિસ ફ્રેચેટ પરથી રાખવામાં આવ્યું છે. સાહજિક વ્યાખ્યા કલ્પના કરો કે એક વ્યક્તિ તેમના કૂતરાને પટ્ટા પર ચાલતી વખતે મર્યાદિત વક્ર માર્ગને પાર કરે છે, જેમાં કૂતરો એક અલગ મર્યાદિત વક્ર માર્ગને પાર કરે છે. દરેક કાબૂમાં રાખવા માટે તેમની ગતિમાં ફેરફાર કરી શકે છે, પરંતુ બંનેમાંથી કોઈ પણ પાછળની તરફ આગળ વધી શકતું નથી. બે વળાંકો વચ્ચેનું ફ્રેચેટ અંતર એ ટૂંકા પટ્ટાની લંબાઈ છે જે બંને માટે શરૂઆતથી અંત સુધી તેમના અલગ માર્ગોને પાર કરવા માટે પૂરતી છે. નોંધ લો કે વ્યાખ્યા બે વળાંકના સંદર્ભમાં સપ્રમાણ છે-જો કૂતરો તેના માલિકને ચાલતા હોય તો ફ્રેચેટ અંતર સમાન હશે. ઔપચારિક વ્યાખ્યા ચાલો મેટ્રિક જગ્યા હોઈએ. એક વળાંક એ એકમ અંતરાલમાંથી, એટલે કે, માં સતત નકશો છે. રિપેરામેટરાઈઝેશન એ સતત, બિન-ઘટતું, સર્જેક્શન છે. ચાલો અને બે વળાંક આપવામાં આવે. પછી, અને વચ્ચેના ફ્રેચેટ અંતરને તમામ રિપેરામેટેરાઇઝેશન પર અનંત અને અને વચ્ચેના તમામ અંતર પર મહત્તમ તરીકે વ્યાખ્યાયિત કરવામાં આવે છે. ગાણિતિક સંકેતલિપીમાં, ફ્રેચેટ અંતર એ છે જ્યાં તેનું અંતર કાર્ય છે. અનૌપચારિક રીતે, આપણે પરિમાણને "સમય" તરીકે વિચારી શકીએ છીએ. પછી, કૂતરાની સ્થિતિ છે અને તે સમયે કૂતરાના માલિકની સ્થિતિ છે (અથવા ઊલટું). સમયે તેમની વચ્ચેની પટ્ટીની લંબાઈ એ અને વચ્ચેનું અંતર છે. તમામ સંભવિત રિપેરામેટ્રિઝેશન્સ પર અનંત લેવું એ આપેલ માર્ગો પર ચાલવાનું પસંદ કરવા જેવું છે જ્યાં મહત્તમ પટ્ટીની લંબાઈ ઘટાડવામાં આવે છે. પ્રતિબંધ કે જે ઘટતો નથી તેનો અર્થ એ છે કે ન તો કૂતરો અને ન તો તેનો માલિક પીછેહઠ કરી શકે છે. ફ્રેચેટ મેટ્રિક બે વળાંકના પ્રવાહને ધ્યાનમાં લે છે કારણ કે બિંદુઓની જોડી કે જેનું અંતર તેમના સંબંધિત વળાંક સાથે સતત ફ્રેચેટ અંતર સ્વીપમાં ફાળો આપે છે. આ ફ્રેચેટ અંતરને વળાંક માટે વિકલ્પોની સરખામણીમાં સમાનતાનું વધુ સારું માપ બનાવે છે, જેમ કે હૌસડોર્ફ અંતર, મનસ્વી બિંદુ સમૂહો માટે. બે વળાંકો માટે હૌસડોર્ફ અંતર નાનું પરંતુ મોટા ફ્રેચેટ અંતર હોવું શક્ય છે. ફ્રેચેટ અંતર અને તેના પ્રકારો મોર્ફિંગ અને હસ્તાક્ષરની ઓળખથી માંડીને પ્રોટીન માળખાના સંરેખણ સુધીની ઘણી સમસ્યાઓમાં લાગુ પડે છે. પેરામેટ્રિક શોધના સિદ્ધાંતના આધારે યુક્લિડિયન અવકાશમાં બે બહુકોણીય વળાંકો વચ્ચેના ફ્રેચેટ અંતરની ગણતરી કરવા માટે બહુપદી-સમય અલ્ગોરિધમનું વર્ણન કરનારા ઓલ્ટ અને ગોડાઉ સૌપ્રથમ હતા. તેમના અલ્ગોરિધમનો ચાલી રહેલો સમય એમ અને એન સેગમેન્ટ્સ સાથે બે બહુકોણીય વળાંક માટે છે. ફ્રી-સ્પેસ આકૃતિ બે વળાંકના ફ્રેચેટ અંતરની ગણતરી કરવા માટેનું એક મહત્વપૂર્ણ સાધન ફ્રી-સ્પેસ આકૃતિ છે, જે અલ્ટ અને ગોડાઉ દ્વારા રજૂ કરવામાં આવી હતી. આપેલ અંતર થ્રેશોલ્ડ ε માટે બે વણાંકો વચ્ચેનો મુક્ત-અવકાશ આકૃતિ એ પરિમાણ જગ્યામાં દ્વિ-પરિમાણીય પ્રદેશ છે જેમાં મહત્તમ ε અંતર પર બે વણાંકો પર તમામ બિંદુ જોડીનો સમાવેશ થાય છેઃ ફ્રેચેટ અંતર મહત્તમ ε હોય છે જો અને માત્ર ત્યારે જ જો મુક્ત-અવકાશ આકૃતિમાં નીચલા ડાબા ખૂણેથી ઉપલા જમણા ખૂણે સુધીનો માર્ગ હોય, જે આડી અને ઊભી બંને દિશામાં એકવિધ હોય. સંભાવના વિતરણ (એફ. આઈ. ડી. સ્કોર) વચ્ચેના અંતર તરીકે વળાંક વચ્ચેના અંતરને માપવા ઉપરાંત, સંભાવના વિતરણ વચ્ચેના તફાવતને માપવા માટે પણ ફ્રેચેટ અંતરનો ઉપયોગ કરી શકાય છે. માધ્યમ અને સહપરિવર્તન મેટ્રિસીસ સાથેના બે બહુપરીમાણીય ગૌસીયન વિતરણો માટે અને આ વિતરણો વચ્ચેનું ફ્રેચેટ અંતર છે. આ અંતર ફ્રેચેટ પ્રારંભ અંતર (એફ. આઈ. ડી.) માટેનો આધાર છે જેનો ઉપયોગ જનરેટિવ પ્રતિકૂળ નેટવર્ક દ્વારા ઉત્પાદિત છબીઓને તાલીમ માટે ઉપયોગમાં લેવાતી વાસ્તવિક છબીઓ સાથે સરખાવવા માટે થાય છે. નબળું ફ્રેચેટ અંતર એ શાસ્ત્રીય ફ્રેચેટ અંતરનો એક પ્રકાર છે, જેમાં અંતિમ બિંદુઓ તેમના સંબંધિત વળાંક સાથે એકવિધ રીતે આગળ વધે તે જરૂરી નથી-કૂતરા અને તેના માલિકને તેમની વચ્ચેની પટ્ટી ટૂંકી રાખવા માટે પીછેહઠ કરવાની મંજૂરી આપવામાં આવે છે. ઓલ્ટ અને ગોડાઉ સંકળાયેલ ગ્રીડ ગ્રાફમાં મિનિમેક્સ પાથની ગણતરીના આધારે બહુકોણીય વળાંક વચ્ચેના નબળા ફ્રેચેટ અંતરની ગણતરી કરવા માટે એક સરળ અલ્ગોરિધમનું વર્ણન કરે છે. અલગ ફ્રેચેટ અંતર, જેને જોડાણ અંતર પણ કહેવામાં આવે છે, તે બહુકોણીય વળાંક માટે ફ્રેચેટ મેટ્રિકનો અંદાજ છે, જે એઇટર અને મનીલા દ્વારા વ્યાખ્યાયિત કરવામાં આવે છે. અલગ ફ્રેચેટ અંતર માત્ર પટ્ટીની સ્થિતિને ધ્યાનમાં લે છે જ્યાં તેના અંતિમ બિંદુઓ બે બહુકોણીય વળાંકના શિરોબિંદુઓ પર સ્થિત હોય અને ક્યારેય ધારની અંદર ન હોય. આ વિશેષ માળખું એક સરળ ગતિશીલ પ્રોગ્રામિંગ અલ્ગોરિધમ દ્વારા બહુપદી સમયમાં અલગ ફ્રેચેટ અંતરની ગણતરી કરવાની મંજૂરી આપે છે. જ્યારે બે વળાંક યુક્લિડિયન જગ્યા સિવાય અન્ય મેટ્રિક જગ્યામાં જડિત હોય છે, જેમ કે પોલિહેડ્રલ ભૂપ્રદેશ અથવા અવરોધો સાથેની કેટલીક યુક્લિડિયન જગ્યા, ત્યારે વળાંક પરના બે બિંદુઓ વચ્ચેનું અંતર સૌથી કુદરતી રીતે તેમની વચ્ચેના ટૂંકા માર્ગની લંબાઈ તરીકે વ્યાખ્યાયિત કરવામાં આવે છે. પટ્ટી તેના અંતિમ બિંદુઓને જોડતી ભૌગોલિક હોવી જરૂરી છે. વળાંક વચ્ચેના પરિણામી મેટ્રિકને જીઓડેસિક ફ્રેચેટ અંતર કહેવામાં આવે છે. કૂક અને વેન્ક એક સરળ બહુકોણમાં બે બહુકોણીય વળાંક વચ્ચેના ભૌગોલિક ફ્રેચેટ અંતરની ગણતરી કરવા માટે બહુપદી-સમય અલ્ગોરિધમનું વર્ણન કરે છે. જો આપણે આગળ જરૂર પડે કે પટ્ટાએ આજુબાજુની મેટ્રિક જગ્યામાં સતત આગળ વધવું જોઈએ, તો આપણે બે વળાંક વચ્ચેના હોમોટોપિક ફ્રેચેટ અંતરની કલ્પના મેળવીએ છીએ. પટ્ટો એક સ્થાનથી બીજા સ્થાને અવિરતપણે ફેરવી શકતો નથી-ખાસ કરીને, પટ્ટો અવરોધો પર કૂદી શકતો નથી, અને જો તે પૂરતો લાંબો હોય તો જ ભૂપ્રદેશ પર પર્વત પર ઝાડી મારી શકે છે. પટ્ટીની ગતિ બે વળાંક વચ્ચેની હોમોટૉપીનું વર્ણન કરે છે. ચેમ્બર્સ વગેરે. યુક્લિડિયન સમતલમાં અવરોધો સાથે બહુકોણીય વળાંક વચ્ચેના સમસ્થાનિક ફ્રેચેટ અંતરની ગણતરી કરવા માટે બહુપદી-સમય અલ્ગોરિધમનું વર્ણન કરો. ઉદાહરણો ત્રિજ્યાના અને અનુક્રમે બે કેન્દ્રિત વર્તુળો વચ્ચેનું ફ્રેચેટ અંતર એ છે કે જ્યારે માલિક સ્થિર રહે છે અને કૂતરો વર્તુળની વિરુદ્ધ બાજુએ પ્રવાસ કરે છે ત્યારે સૌથી લાંબો પટ્ટા જરૂરી છે, અને જ્યારે માલિક અને કૂતરો બંને વર્તુળની આસપાસ સતત કોણીય વેગથી ચાલે છે ત્યારે સૌથી ટૂંકો પટ્ટા જરૂરી છે. એપ્લિકેશન્સ ફ્રેચેટ અંતરનો ઉપયોગ દ્રશ્ય પદાનુક્રમનો અભ્યાસ કરવા માટે કરવામાં આવ્યો છે, જે એક ગ્રાફિક ડિઝાઇન સિદ્ધાંત છે. ફ્રેચેટ શરૂઆત અંતર ફ્રેચેટ અર્થ સંદર્ભો વધુ વાંચન પણ જુઓ. . . મેટ્રિક ભૂમિતિ અંતર ટોપોલોજી ભૌમિતિક ગાણિતીક નિયમો