Kinetic closest pair
একটি কাইনেটিক নিকটতম জোড়া ডেটা স্ট্রাকচার হল একটি কাইনেটিক ডেটা স্ট্রাকচার যা নিকটতম জোড়া পয়েন্ট বজায় রাখে, একটি মেট্রিক স্পেসে সময়ের সাথে অবিচ্ছিন্নভাবে চলমান এন পয়েন্টের একটি সেট পি দেওয়া হয়। যদিও স্ট্যাটিক ক্ষেত্রে অনেক দক্ষ অ্যালগরিদম জানা ছিল, সেগুলি কাইনেটাইজ করা কঠিন প্রমাণিত হয়েছিল, তাই এই সমস্যা সমাধানের জন্য নতুন স্ট্যাটিক অ্যালগরিদম তৈরি করা হয়েছিল। 2ডি কেস অ্যাপ্রোচ 1 নিকটতম জুটির রক্ষণাবেক্ষণের জন্য সবচেয়ে সহজ গতিবিদ্যার পদ্ধতি হল ডেলাউনে ত্রিভুজের রূপগুলি ব্যবহার করা। একটি ষড়ভুজ বিবেচনা করুন এবং এটিকে ছয়টি সমবাহু ত্রিভুজে বিভক্ত করুন, এবং তারপর প্রতিটি সমবাহু ত্রিভুজের উপর ভিত্তি করে একটি ডেলাউনে ত্রিভুজ তৈরি করুন, কারণ প্রতিটি একটি উত্তল আকৃতি। এই ছয়টি ডেলাউনে ত্রিভুজের মিলন, যাকে ইকুইল্যাটারাল ডেলাউনে গ্রাফ (ইডিজি) বলা হয়, নিকটতম প্রতিবেশী গ্রাফের (এনএনজি) জন্য একটি সুপারগ্রাফ; ইডিজিতে ন্যূনতম দৈর্ঘ্য সহ প্রান্তের শেষ বিন্দুগুলি নিকটতম জোড়া দেয়। উত্তল আকৃতির উপর ভিত্তি করে ডেলাউনে ত্রিভুজ বজায় রাখা সোজা। সময়ের সাথে সাথে ইডিজির পরিপ্রেক্ষিতে, ইডিজির প্রান্তে একটি কাইনেটিক টুর্নামেন্ট ট্রি তৈরি করে, কেউ সহজেই নিকটতম জোড়া বজায় রাখতে পারে। এই নিকটতম জোড়া কে. ডি. এস দক্ষ, ঋণ পরিশোধিত প্রতিক্রিয়াশীল এবং সংক্ষিপ্ত, তবে সাধারণভাবে স্থানীয় নয়। নিম্নলিখিত পদ্ধতিটি নিকটতম জুটির রক্ষণাবেক্ষণের জন্য একটি স্থানীয় কে. ডি. এস উপস্থাপন করে। পদ্ধতি 2 দ্বিতীয় গতিবিদ্যার পদ্ধতিটি নিম্নলিখিত পর্যবেক্ষণগুলির উপর ভিত্তি করে তৈরি। ভাগ করুন এবং জয় করুন যদি একটি বিন্দুর চারপাশের স্থানটি কৌণিকভাবে ছয়টি "ওয়েজ"-এ বিভক্ত করা হয়, প্রতিটি প্রশস্ত, প্রতিটি ওয়েজের নিকটতম বিন্দু হল নিকটতম পয়েন্ট। এই নিবন্ধের বাকি অংশটি "প্রধান" ওয়েজগুলির (যেগুলি এক্স-অক্ষ দ্বারা দ্বিখণ্ডিত) উপর দৃষ্টি নিবদ্ধ করবে এবং সমতলটি ঘোরানোর পরে অন্যান্য ওয়েজের ক্ষেত্রে প্রতিসম আর্গুমেন্টগুলি প্রযোজ্য হবে। ম্যাচ পয়েন্ট পয়েন্ট এবং একে অপরের নিকটতম পয়েন্ট হলে "ম্যাচ" বলা হয়। স্পষ্টতই, পয়েন্টের নিকটতম জোড়া হল একটি মিলে যাওয়া জোড়া। পয়েন্টগুলি বিবেচনা করুন এবং, যেমন বাম দিকে এবং উপরে বর্ণিত কেন্দ্রিক পাঁজরের মধ্যে অবস্থিত। যদি নিকটতম বিন্দু হয়, তাহলে অবশ্যই x-দিকের নিকটতম বিন্দু (এই পাঁজরের মধ্যে) হতে হবে। সুতরাং, x-দিকে নিকটতম বিন্দুর জোড়ার সেট (এই পাঁজরের মধ্যে) হল নিকটতম বিন্দুর জোড়ার সেটের একটি সুপারসেট। সেট পি-তে প্রতিটি বিন্দু পি = (এক্স, ওয়াই)-কে একটি নতুন বিন্দুতে মানচিত্র তৈরি করুন, যা রূপান্তরিত বিন্দুর সেট পি 'গঠন করে। লক্ষ্য করুন যে একটি বিন্দুর জন্য, "প্রধান" পাঁজরের বিন্দুগুলির স্থানাঙ্ক এই নতুন স্থানাঙ্ক ব্যবস্থার চেয়ে বড় বা ছোট হয়। x, u এবং v স্থানাঙ্ক দ্বারা বিন্দুগুলিকে সাজান এবং সেগুলিকে গতিজ সাজানো তালিকায় সংরক্ষণ করুন। ভিতরের বিন্দুতে একটি 2ডি রেঞ্জ ট্রি টি তৈরি করুন। প্রাথমিক গাছের প্রতিটি নোড ডাব্লু-এর জন্য, টি (ডাব্লু) ডাব্লু-এর সাথে সম্পর্কিত গৌণ গাছ হতে দিন। এই পরিসীমা গাছটি একটি বিন্দুর জন্য "প্রধান" পাঁজরের বিন্দুগুলি সনাক্ত করতে ব্যবহৃত হবে। প্রাথমিক গাছের প্রতিটি নোডের জন্য এবং টি (ডাব্লু)-এর প্রতিটি নোডের জন্য, জোড়া (ডাব্লু, ই) = (বি, আর) গণনা করুন, যেখানে বি (বা আর) কে ই-এর বাম (বা ডান) সাবট্রিতে সর্বাধিক (বা সর্বনিম্ন) এক্স-সমন্বিত বিন্দু হিসাবে সংজ্ঞায়িত করা হয়। ধরা যাক সমস্ত জোড়ার জন্য (ডাব্লু, ই) সেট হতে হবে ডাব্লু, ই টি-তে। এটি নিকটতম পয়েন্টের জোড়ার সেটের একটি সুপারসেট (প্রধান পাঁজরের মধ্যে)। জোড়াগুলির মধ্যে একটি গতিজ অগ্রাধিকার সারি তৈরি করুন, যেখানে জোড়াগুলির মধ্যে দূরত্ব (মূল সমন্বয় ব্যবস্থায় পরিমাপ করা) দ্বারা অগ্রাধিকারগুলি নির্ধারিত হয়। বিমানটি ঘোরানোর জন্য উপরের ধাপগুলি পুনরাবৃত্তি করুন, যাতে গতিবিদ্যার অগ্রাধিকারের সারিগুলি যথাক্রমে চালু থাকে। পি-তে নিকটতম জোড়া পয়েন্ট উপরের তিনটি অগ্রাধিকার সারি থেকে প্রাপ্ত সর্বনিম্ন পয়েন্টের সাথে মিলে যায়। রক্ষণাবেক্ষণ শংসাপত্রের ব্যর্থতা অগ্রাধিকার সারি এবং সাজানো তালিকাগুলিতে ঘটতে পারে। পয়েন্টের ক্রমানুসারে অদলবদল টি-তে পরিবর্তন ঘটাবে (যা সময় নেবে), এবং অগ্রাধিকার সারিতে সন্নিবেশ/মুছে ফেলার কারণ হতে পারে। মনে রাখবেন যে উপরে বর্ণিত সেটগুলিতে পরিবর্তনের সংখ্যা একটি ধ্রুবক সংখ্যা হওয়ার প্রয়োজন নেই। যাইহোক, যে কোনও জোড়া যা পি এবং কিউ পরিবর্তনের ক্রমের ফলস্বরূপ মিলে যাওয়া শুরু করে বা বন্ধ করে দেয় তাতে অবশ্যই পি এবং/অথবা কিউ থাকতে হবে এবং তাই কেবলমাত্র সামঞ্জস্যপূর্ণ জোড়ার একটি ধ্রুবক সংখ্যা রয়েছে যা অগ্রাধিকার সারিতে ঢোকানো/মুছে ফেলা আবশ্যক। শুধুমাত্র এই মিলে যাওয়া জোড়াগুলিকে আপডেট করা ঠিক আছে, কারণ সংজ্ঞা অনুসারে, শুধুমাত্র মিলে যাওয়া জোড়াগুলিরই নিকটতম জোড়া হওয়ার সম্ভাবনা থাকে। এই কে. ডি. এস বিশ্লেষণটি হলঃ প্রতিক্রিয়াশীলঃ একটি ইভেন্ট প্রক্রিয়া করতে সময় নেয় স্থানীয়ঃ যেহেতু প্রতিটি বিন্দু স্থির সংখ্যক গতিজ সাজানো তালিকা এবং গতিজ অগ্রাধিকার সারিতে উপস্থিত থাকে, তাই সেই কাঠামোগুলির অবস্থান থেকে স্থানীয়তা অনুসরণ করা হয় সংক্ষিপ্ততাঃ গতিজ সাজানো তালিকা এবং গতিজ অগ্রাধিকার সারির সংক্ষিপ্ততা থেকে সংক্ষিপ্ততা অনুসরণ করা হয় দক্ষঃ সাজানো তালিকার প্রতিটি অদলবদল গতিজ অগ্রাধিকার সারিতে অবিচ্ছিন্ন সংখ্যক সন্নিবেশ এবং মুছে ফেলার কারণ হয়। বিন্দুগুলির গতি ছদ্ম-বীজগাণিতিক বলে ধরে নিলে, একটি বহুপদী সংখ্যক অদলবদল রয়েছে এবং তাই এই কে. ডি. এস দ্বারা একটি বহুপদী সংখ্যক ঘটনা প্রক্রিয়া করা হয়, যা এটিকে দক্ষ করে তোলে এই পদ্ধতিটি উচ্চতর মাত্রায় নিকটতম জোড়া বজায় রাখতে ব্যবহার করা যেতে পারে। তথ্যসূত্র গতিজ তথ্য কাঠামো জ্যামিতিক তথ্য কাঠামো