Kinetic convex hull
একটি কাইনেটিক কনভেক্স হুল ডেটা স্ট্রাকচার হল একটি কাইনেটিক ডেটা স্ট্রাকচার যা ক্রমাগত চলমান পয়েন্টগুলির একটি সেটের কনভেক্স হুল বজায় রাখে। এটি গতিশীল উত্তল হুল ডেটা স্ট্রাকচার থেকে আলাদা করা উচিত, যা অবিচ্ছিন্ন গতির পরিবর্তে পয়েন্ট সন্নিবেশ বা মুছে ফেলার মতো বিচ্ছিন্ন পরিবর্তনের মধ্য দিয়ে যাওয়া পয়েন্টগুলি পরিচালনা করে। 2ডি কেস 2-মাত্রিক উত্তল কাঠামো সমস্যার জন্য সবচেয়ে বেশি পরিচিত তথ্য কাঠামো হল বাস্চ, গুইবাস এবং হার্শবার্গার। এই তথ্য কাঠামোটি প্রতিক্রিয়াশীল, দক্ষ, সংক্ষিপ্ত এবং স্থানীয়। তথ্য কাঠামো বিন্দুগুলির একটি সেটের উত্তল কাঠামোর দ্বৈত হল দ্বৈত লাইনের সেটের উপরের এবং নীচের খাম। অতএব, চলন্ত রেখার একটি সেটের উপরের এবং নীচের খামগুলি বজায় রাখা চলন্ত বিন্দুর একটি সেটের উত্তল কাঠামো বজায় রাখার সমতুল্য। উপরের এবং নীচের খামগুলি গণনা করা সমতুল্য সমস্যা, তাই একটি লাইনের সেটের উপরের খামটি গণনা করা চলন্ত বিন্দুর একটি সেটের উত্তল হুল গণনা করার সমতুল্য। স্থির রেখার একটি সেটের উপরের খামটি একটি বিভাজন এবং জয় অ্যালগরিদম ব্যবহার করে গণনা করা যেতে পারে যা লাইনগুলিকে সমান আকারের দুটি সেটে বিভক্ত করে, তাদের উপরের খামগুলি খুঁজে বের করার জন্য দুটি সেটে নিজেকে পুনরাবৃত্তভাবে কল করে এবং তারপরে দুটি ফলস্বরূপ একত্রিত করে উপরের খামগুলি। মার্জ ধাপটি একটি উল্লম্ব লাইন সুইপ ব্যবহার করে সঞ্চালিত হয়। পয়েন্টের প্রথম সেটকে নীল এবং দ্বিতীয় সেটকে লাল বলুন। উপরের খামগুলিকে একত্রিত করার জন্য স্ট্যান্ডার্ড লাইন সুইপ অ্যালগরিদম বাম থেকে ডানদিকে লাল এবং নীল উপরের খামের সমস্ত শীর্ষে সুইপ করে। সাম্প্রতিককালে সম্মুখীন হওয়া লাল এবং নীল পয়েন্টগুলি লাইন সুইপ হিসাবে রক্ষণাবেক্ষণ করা হয়। যখন কোনও বিন্দুর মুখোমুখি হয়, তখন অ্যালগরিদম পরীক্ষা করে যে বিপরীত রঙের শেষ মুখোমুখি বিন্দুর পরে বিন্দুটি বিভাগের উপরে বা নীচে রয়েছে কিনা। যদি এটি উপরে থাকে, তবে সেই বিন্দুটি সংযুক্ত উপরের খামে যোগ করা হয়। যদি এটি শেষ যুক্ত বিন্দুর থেকে ভিন্ন রঙের হয়, তবে লাল এবং নীল খামগুলি অতিক্রম করেছে, তাই ছেদ বিন্দুটিও সংযুক্ত উপরের খামে যোগ করা হয়েছে। এই অ্যালগরিদম থেকে প্রাপ্ত প্রান্ত এবং শীর্ষগুলির ক্রম শুধুমাত্র বিন্দুর ক্রম এবং লাইন-পয়েন্ট তুলনার ফলাফলের উপর নির্ভরশীল। সুতরাং, ফলাফলটি নিম্নলিখিত শংসাপত্রগুলির সাথে প্রত্যয়িত করা যেতে পারেঃ x-শংসাপত্রগুলি () লাল এবং নীল খামের শীর্ষগুলি প্রত্যয়িত করতে ব্যবহৃত হয়। এগুলি শীর্ষগুলির সেটে একটি গতিময় সাজানো তালিকার শংসাপত্র। যেহেতু প্রতিটি পয়েন্টে 2টি লাইন থাকে এবং শংসাপত্রে 2টি পয়েন্ট থাকে, তাই প্রতিটি শংসাপত্রে 4টি লাইন থাকে। একটি শীর্ষ একটি প্রান্তের উপরে বা নীচে রয়েছে তা প্রত্যয়িত করতে y-শংসাপত্র () ব্যবহার করা হয়। অ্যালগরিদম চলাকালীন ঘটে যাওয়া সমস্ত তুলনার জন্য শংসাপত্রগুলি উপস্থিত হয়। যতক্ষণ পর্যন্ত এই সমস্ত শংসাপত্রগুলি ধরে থাকবে, ততক্ষণ সংযুক্তির পদক্ষেপগুলি একইভাবে কার্যকর করা হবে, যার ফলে উপরের খামটি একই থাকবে। স্ট্যাটিক আপার এনভেলপ অ্যালগরিদমকে প্রত্যয়িত করতে এই শংসাপত্রগুলি ব্যবহার করে উপরের এনভেলপের জন্য একটি কাইনেটিক ডেটা স্ট্রাকচার তৈরি করা যেতে পারে। যাইহোক, এই স্কিমটি স্থানীয় নয়, কারণ একটি লাইন অনেকগুলি ওয়াই-শংসাপত্রের সাথে জড়িত থাকে যদি এটি উপরে বা নীচে থাকে তবে অন্য খাম থেকে অনেক পয়েন্টের মুখোমুখি হয়। সুতরাং, একটি এস-শংসাপত্র () প্রবর্তন করা প্রয়োজন যা প্রত্যয়িত করে যে একটি রেখার ঢাল অন্য রেখার ঢালের চেয়ে বড় বা কম। সমস্ত পয়েন্টের জন্য নিম্নলিখিত শংসাপত্রগুলি থাকা একটি সংযুক্তির ফলে প্রান্ত এবং শীর্ষগুলির ক্রমকে প্রত্যয়িত করার জন্য যথেষ্ট, প্রতি লাইনে কেবল ও (1) শংসাপত্র সহঃ এর ডানদিকের নিকটতম শীর্ষকে বোঝায়। এই শংসাপত্রটি সমস্ত পয়েন্টের জন্য সংরক্ষণ করা হয় যার পয়েন্টের চেয়ে আলাদা রঙ রয়েছে, যা তাদের অনুসরণ করে। : অথবা। এই শংসাপত্রটি এমন সমস্ত পয়েন্টের জন্য সংরক্ষণ করা হয় যা ছেদ করে। প্রতিযোগী প্রান্তকে নির্দেশ করে, অন্য খামের প্রান্ত যা উপরে বা নীচে রয়েছে। : অথবা। এই শংসাপত্রটি এমন সমস্ত পয়েন্টের জন্য সংরক্ষণ করা হয় যা ছেদ করে। :। এই শংসাপত্রটি সমস্ত পয়েন্টের জন্য সংরক্ষণ করা হয় যার জন্য এবং। :। এই শংসাপত্রটি সমস্ত পয়েন্টের জন্য সংরক্ষণ করা হয় যার জন্য এবং। :। এই শংসাপত্রটি সমস্ত পয়েন্টের জন্য সংরক্ষণ করা হয় যার জন্য এবং। :। এই শংসাপত্রটি সমস্ত পয়েন্টের জন্য সংরক্ষণ করা হয় যার জন্য এবং। :। এই শংসাপত্রটি সমস্ত পয়েন্টের জন্য সংরক্ষণ করা হয় যার জন্য এবং। প্রথম শংসাপত্রটি, লাল এবং নীল খামে পয়েন্টগুলির এক্স-অর্ডারিংকে প্রত্যয়িত করে। দ্বিতীয় এবং তৃতীয় শংসাপত্র, এবং, লাল এবং নীল খামের ছেদকে প্রত্যয়িত করে। বাকি 5টি শংসাপত্র,,,, এবং উপরের খামে না থাকা প্রান্তগুলি উপরের প্রান্তগুলির ঢালের ক্রমে স্থাপন করুন। যদি ঢালটি অনুক্রমের শুরুতে বা শেষে থাকে, অথবা এটি প্রত্যয়িত করুন। যদি এটি ক্রমের মাঝখানে থাকে, এবং এটি প্রত্যয়িত করে, এবং প্রত্যয়িত করে যে দুটি রেখার ছেদ বিন্দু যে প্রান্তের ঢালটি এর মধ্যে রয়েছে, তার উপরে রয়েছে। এই এক বা তিনটি শংসাপত্র প্রমাণ করার জন্য যথেষ্ট যে সমস্ত প্রান্ত এই রেখার উপরে রয়েছে। পূর্ববর্তী পরিকল্পনার বিপরীতে সমস্ত লাইন শুধুমাত্র একটি ধ্রুবক সংখ্যক শংসাপত্রের সাথে জড়িত। যখনই এই শংসাপত্রগুলির মধ্যে ব্যর্থ হয়, তখন সংযুক্ত খাম এবং শংসাপত্রগুলি ও (1) সময়ে আপডেট করা যেতে পারে। উত্তল কাঠামোর জন্য গতিজ তথ্য কাঠামো এই শংসাপত্রগুলি ব্যবহার করে উপরের খামগুলির পুনরাবৃত্তিমূলক সংমিশ্রণকে প্রত্যয়িত করার জন্য তৈরি করা হয়। যখনই শংসাপত্রগুলি ব্যর্থ হয়, তাদের একত্রীকরণ আপডেট করা হয় এবং যদি একত্রীকরণের ফলে খামটি পরিবর্তিত হয়, তবে পরিবর্তনগুলি সমস্ত একত্রীকরণের মাধ্যমে প্রচারিত হয় যা একত্রীকরণের ফলাফলের উপর নির্ভর করে। কর্মক্ষমতা এই তথ্য কাঠামোটি প্রতিক্রিয়াশীল, স্থানীয়, সংক্ষিপ্ত এবং দক্ষ। এটি উপরের খামটি প্রত্যয়িত করতে ব্যবহৃত সংযুক্তিগুলির লগারিদমিক গভীরতার কারণে হয়। প্রতিক্রিয়াশীলঃ যখন একটি শংসাপত্র ব্যর্থ হয়, তখন এটি প্রত্যয়িত মার্জটি ঠিক করতে ও (1) লাগে। যদি ফলস্বরূপ খামটি পরিবর্তিত হয়, তবে পরিবর্তনটি অবশ্যই সমস্ত সংযুক্তি পর্যন্ত প্রচার করা উচিত যা পরিবর্তিত সংযুক্তির ফলাফলের উপর নির্ভর করে। এই ধরনের ও (লগ এন) সংযুক্তি রয়েছে, তাই আপডেটটি মোট ও (লগ এন) সময়ে করা যেতে পারে। স্থানীয়ঃ প্রতিটি লাইন সর্বাধিক ও (লগ এন) শংসাপত্রের সাথে জড়িত। এর কারণ হল প্রতিটি লাইন প্রতিটি সংযুক্তিতে ধ্রুবক সংখ্যক শংসাপত্রের সাথে জড়িত থাকে এবং প্রতিটি লাইন মোট ও (লগ এন) সংযুক্তিতে থাকে। সংক্ষিপ্ততাঃ এই তথ্য কাঠামোতে ব্যবহৃত শংসাপত্রের সর্বাধিক সংখ্যা হল ও (এন লগ এন)। এর কারণ হল, প্রতিটি একত্রীকরণে একাধিক শংসাপত্র যুক্ত থাকে, যা একত্রীকরণের লাইনের সংখ্যার সঙ্গে রৈখিক। এন লাইনের একটি উপরের খামের শংসাপত্রের জন্য এন/2 লাইনের দুটি উপসেটগুলির সংযুক্ত উপরের খামের শংসাপত্র এবং খামগুলির সংযুক্তির শংসাপত্র প্রয়োজন। সুতরাং এন লাইনের উপরের খামটি প্রত্যয়িত করার জন্য প্রয়োজনীয় শংসাপত্রের সংখ্যা, সি (এন), সি (1) = ও (1) সহ পুনরাবৃত্তি সি (এন) = 2সি (এন/2) + ও (এন) কে সন্তুষ্ট করে। বিভাজন ও জয় পুনরাবৃত্তির প্রধান উপপাদ্য অনুসারে, সি (এন) = ও (এন লগ এন)। দক্ষতাঃ বীজগাণিতিক বা ছদ্ম-বীজগাণিতিক গতিপথের উপর এই অ্যালগরিদম দ্বারা প্রক্রিয়াজাত সর্বাধিক সংখ্যক ঘটনা সকলের জন্য প্রায় দ্বিঘাত। রৈখিকভাবে চলমান বিন্দুর কনভেক্স হুলগুলি সময় পরিবর্তন করতে পারে। সুতরাং এই তথ্য কাঠামো কার্যকরী। 2-এর চেয়ে বেশি মাত্রায় চলমান বিন্দুর উত্তল কাঠামো বজায় রাখার জন্য একটি দক্ষ গতিজ তথ্য কাঠামো খুঁজে পাওয়া একটি উন্মুক্ত সমস্যা। সম্পর্কিত সমস্যা কাইনেটিক কনভেক্স হুল নিম্নলিখিত সম্পর্কিত সমস্যাগুলি সমাধান করতে ব্যবহার করা যেতে পারেঃ কাইনেটিক ব্যাস কাইনেটিক প্রস্থ কাইনেটিক ন্যূনতম বাক্স কাইনেটিক ক্ষুদ্রতম এনক্লোজিং ডিস্ক রেফারেন্স কাইনেটিক ডেটা স্ট্রাকচার কনভেক্স হুল অ্যালগরিদম