Fréchet distance
গণিতে, ফ্রেচেট দূরত্ব হল বক্ররেখার মধ্যে সাদৃশ্যের একটি পরিমাপ যা বক্ররেখা বরাবর বিন্দুর অবস্থান এবং ক্রমকে বিবেচনা করে। এটি মরিস ফ্রেচেটের নামে নামকরণ করা হয়েছে। স্বজ্ঞাত সংজ্ঞা কল্পনা করুন যে একজন ব্যক্তি একটি সীমাবদ্ধ বাঁকানো পথ অতিক্রম করছে যখন তাদের কুকুরটিকে একটি শিকলের উপর দিয়ে হাঁটছে, কুকুরটি একটি পৃথক সীমাবদ্ধ বাঁকানো পথ অতিক্রম করছে। লেশে শিথিল রাখার জন্য প্রত্যেকে তাদের গতি পরিবর্তন করতে পারে, তবে কেউই পিছন দিকে এগোতে পারে না। দুটি বক্ররেখার মধ্যে ফ্রেচেট দূরত্ব হল সংক্ষিপ্ততম শিকলের দৈর্ঘ্য যা উভয়ের জন্য শুরু থেকে শেষ পর্যন্ত তাদের পৃথক পথ অতিক্রম করার জন্য যথেষ্ট। লক্ষ্য করুন যে সংজ্ঞাটি দুটি বক্ররেখার ক্ষেত্রে প্রতিসম-ফ্রেচেট দূরত্ব একই হবে যদি কুকুরটি তার মালিককে হাঁটতে থাকে। আনুষ্ঠানিক সংজ্ঞা ধরা যাক একটি মেট্রিক স্থান। একটি বক্ররেখা হল একক ব্যবধান থেকে, অর্থাৎ, একটি অবিচ্ছিন্ন মানচিত্র। একটি রিপ্যারামিটারাইজেশন হল একটি অবিচ্ছিন্ন, অ-হ্রাসকারী, সারজেকশন। ধরা যাক এবং দুটি বক্ররেখা দেওয়া আছে। তারপর, এবং-এর মধ্যে ফ্রেচেট দূরত্বকে সমস্ত মেরামতের উপর অসীম এবং এবং-এর মধ্যে সমস্ত দূরত্বের উপর সর্বাধিক হিসাবে সংজ্ঞায়িত করা হয়। গাণিতিক স্বরলিপিতে, ফ্রেচেট দূরত্ব হল যেখানে এর দূরত্ব ফাংশন। অনানুষ্ঠানিকভাবে, আমরা পরামিতিটিকে "সময়" হিসাবে ভাবতে পারি। তারপর, কুকুরের অবস্থান এবং সেই সময়ে কুকুরের মালিকের অবস্থান (বা তদ্বিপরীত)। সময়ে তাদের মধ্যে শিকলের দৈর্ঘ্য হল এবং এর মধ্যে দূরত্ব। সমস্ত সম্ভাব্য মেরামতের উপর অসীম গ্রহণ করা প্রদত্ত পথগুলি বরাবর হাঁটা বেছে নেওয়ার সাথে সামঞ্জস্যপূর্ণ যেখানে সর্বাধিক শিকলের দৈর্ঘ্য হ্রাস করা হয়। যে সীমাবদ্ধতা এবং হ্রাস না হওয়ার অর্থ হল কুকুর বা তার মালিক কেউই পিছু হটতে পারবে না। ফ্রেচেট মেট্রিক দুটি বক্ররেখার প্রবাহকে বিবেচনায় নেয় কারণ পয়েন্টের জোড়া যার দূরত্ব ফ্রেচেট দূরত্বকে তাদের নিজ নিজ বক্ররেখা বরাবর অবিচ্ছিন্নভাবে প্রবাহিত করতে অবদান রাখে। এটি স্বেচ্ছাচারী বিন্দু সেটগুলির জন্য হাউসডর্ফ দূরত্বের মতো বিকল্পগুলির তুলনায় ফ্রেচেট দূরত্বকে বক্ররেখার জন্য সাদৃশ্যের একটি ভাল পরিমাপ করে তোলে। দুটি বক্ররেখার জন্য ছোট হাউজডর্ফ দূরত্ব কিন্তু বড় ফ্রেচেট দূরত্ব থাকা সম্ভব। ফ্রেচেট দূরত্ব এবং এর রূপগুলি মরফিং এবং হাতের লেখার স্বীকৃতি থেকে শুরু করে প্রোটিন কাঠামোর সারিবদ্ধকরণ পর্যন্ত বেশ কয়েকটি সমস্যায় প্রয়োগ খুঁজে পায়। প্যারামেট্রিক অনুসন্ধানের নীতির উপর ভিত্তি করে ইউক্লিডিয়ান স্পেসে দুটি বহুভুজ বক্ররেখার মধ্যে ফ্রেচেট দূরত্ব গণনা করার জন্য অল্ট এবং গোডাউ প্রথম একটি বহুপদী-সময় অ্যালগরিদম বর্ণনা করেছিলেন। তাদের অ্যালগরিদমের চলমান সময় হল এম এবং এন বিভাগ সহ দুটি বহুভুজ বক্ররেখার জন্য। মুক্ত-স্থান রেখাচিত্র দুটি বক্ররেখার ফ্রেচেট দূরত্ব গণনার একটি গুরুত্বপূর্ণ হাতিয়ার হল মুক্ত-স্থান রেখাচিত্র, যা অল্ট এবং গোডাউ দ্বারা প্রবর্তিত হয়েছিল। প্রদত্ত দূরত্বের প্রান্তিকের জন্য দুটি বক্ররেখার মধ্যে মুক্ত-স্থান রেখাচিত্র হল পরামিতি স্থানের একটি দ্বি-মাত্রিক অঞ্চল যা সর্বাধিক ε দূরত্বে দুটি বক্ররেখার সমস্ত বিন্দু জোড়া নিয়ে গঠিতঃ ফ্রেচেট দূরত্ব সর্বাধিক ε হয় যদি এবং শুধুমাত্র যদি মুক্ত-স্থান রেখাচিত্রে নীচের বাম কোণ থেকে উপরের ডান কোণে একটি পথ থাকে, যা অনুভূমিক এবং উল্লম্ব উভয় দিকেই একমুখী হয়। সম্ভাব্যতা বিতরণের মধ্যে দূরত্ব হিসাবে (এফ. আই. ডি স্কোর) বক্ররেখার মধ্যে দূরত্ব পরিমাপ করার পাশাপাশি, সম্ভাব্যতা বিতরণের মধ্যে পার্থক্য পরিমাপ করতে ফ্রেচেট দূরত্বও ব্যবহার করা যেতে পারে। মাধ্যম এবং সহপরিবর্তন ম্যাট্রিক্স সহ দুটি মাল্টিভ্যারিয়েট গাউসিয়ান ডিস্ট্রিবিউশনের জন্য এবং এই ডিস্ট্রিবিউশনের মধ্যে ফ্রেচেট দূরত্ব হল। এই দূরত্বটি ফ্রেচেট সূচনা দূরত্বের (এফ. আই. ডি) ভিত্তি যা একটি উৎপাদক প্রতিকূল নেটওয়ার্ক দ্বারা উত্পাদিত চিত্রগুলির সাথে প্রশিক্ষণের জন্য ব্যবহৃত প্রকৃত চিত্রগুলির তুলনা করতে ব্যবহৃত হয়। দুর্বল ফ্রেচেট দূরত্ব হল ধ্রুপদী ফ্রেচেট দূরত্বের একটি বৈকল্পিক যা শেষ বিন্দুগুলি তাদের নিজ নিজ বক্ররেখা বরাবর একঘেয়েভাবে সরানোর প্রয়োজন ছাড়াই-কুকুর এবং তার মালিককে তাদের মধ্যে শিকলটি ছোট রাখার জন্য ব্যাকট্র্যাক করার অনুমতি দেওয়া হয়। অল্ট এবং গোডাউ একটি সম্পর্কিত গ্রিড গ্রাফে মিনিম্যাক্স পথ গণনা করার উপর ভিত্তি করে বহুভুজাকার বক্ররেখার মধ্যে দুর্বল ফ্রেচেট দূরত্ব গণনা করার জন্য একটি সহজ অ্যালগরিদম বর্ণনা করেছেন। বিচ্ছিন্ন ফ্রেচেট দূরত্ব, যাকে কাপলিং দূরত্বও বলা হয়, এটি আইটার এবং ম্যানিলা দ্বারা সংজ্ঞায়িত বহুভুজাকার বক্ররেখার জন্য ফ্রেচেট মেট্রিকের একটি আনুমানিক মান। বিচ্ছিন্ন ফ্রেচেট দূরত্ব শুধুমাত্র শিকলের অবস্থান বিবেচনা করে যেখানে এর শেষ বিন্দুগুলি দুটি বহুভুজাকার বক্ররেখার শীর্ষে অবস্থিত এবং কোনও প্রান্তের অভ্যন্তরে নয়। এই বিশেষ কাঠামোটি একটি সহজ গতিশীল প্রোগ্রামিং অ্যালগরিদম দ্বারা বহুপদী সময়ে বিচ্ছিন্ন ফ্রেচেট দূরত্ব গণনা করার অনুমতি দেয়। যখন দুটি বক্ররেখা ইউক্লিডীয় স্থান ব্যতীত অন্য কোনও মেট্রিক স্থানে এম্বেড করা হয়, যেমন একটি পলিহেড্রাল ভূখণ্ড বা বাধা সহ কিছু ইউক্লিডীয় স্থান, তখন বক্ররেখার দুটি বিন্দুর মধ্যে দূরত্বকে স্বাভাবিকভাবেই তাদের মধ্যে সংক্ষিপ্ততম পথের দৈর্ঘ্য হিসাবে সংজ্ঞায়িত করা হয়। শিকলটি তার শেষ বিন্দুতে যোগ দেওয়ার জন্য একটি জিওডেসিক হতে হবে। বক্ররেখার মধ্যে ফলস্বরূপ মেট্রিককে জিওডেসিক ফ্রেচেট দূরত্ব বলা হয়। কুক এবং ওয়েঙ্ক একটি সরল বহুভুজের দুটি বহুভুজ বক্ররেখার মধ্যে ভূগাণিতিক ফ্রেচেট দূরত্ব গণনা করার জন্য একটি বহুপদী-সময় অ্যালগরিদম বর্ণনা করেছেন। যদি আমাদের আরও প্রয়োজন হয় যে শিকলটি অবশ্যই পরিবেষ্টিত মেট্রিক স্পেসে অবিচ্ছিন্নভাবে চলতে হবে, তবে আমরা দুটি বক্ররেখার মধ্যে সমস্থানিক ফ্রেচেট দূরত্বের ধারণাটি পাই। জালটি এক অবস্থান থেকে অন্য অবস্থানে অবিচ্ছিন্নভাবে পরিবর্তিত হতে পারে না-বিশেষত, জালটি বাধা অতিক্রম করতে পারে না এবং যথেষ্ট দীর্ঘ হলে কেবল একটি ভূখণ্ডের পাহাড়ের উপর দিয়ে ঝাঁপিয়ে পড়তে পারে। শিকলের গতি দুটি বক্ররেখার মধ্যে একটি সমস্থানিক বর্ণনা করে। চেম্বারস এবং অন্যান্য। ইউক্লিডীয় সমতলে বহুভুজাকার বক্ররেখার মধ্যে সমস্থানিক ফ্রেচেট দূরত্ব গণনা করার জন্য একটি বহুপদী-সময়ের অ্যালগরিদম বর্ণনা করুন। উদাহরণস্বরূপ ব্যাসার্ধের দুটি কেন্দ্রীভূত বৃত্তের মধ্যে এবং যথাক্রমে ফ্রেচেট দূরত্ব হল দীর্ঘতম শিকলের প্রয়োজন হয় যখন মালিক স্থির হয়ে দাঁড়ায় এবং কুকুরটি বৃত্তের বিপরীত দিকে ভ্রমণ করে (), এবং সংক্ষিপ্ততম শিকল যখন মালিক এবং কুকুর উভয়ই বৃত্তের চারপাশে ধ্রুবক কৌণিক গতিতে হাঁটেন ()। অ্যাপ্লিকেশন ফ্রেচেট দূরত্ব ভিজ্যুয়াল শ্রেণিবিন্যাস অধ্যয়নের জন্য ব্যবহৃত হয়েছে, যা একটি গ্রাফিক ডিজাইনের নীতি। আরও দেখুন ফ্রেচেট প্রতিষ্ঠার দূরত্ব ফ্রেচেট মানে রেফারেন্স আরও পড়া। । । মেট্রিক জ্যামিতি দূরত্ব টপোলজি জ্যামিতিক অ্যালগরিদম