Klee's measure problem
গণনামূলক জ্যামিতিতে, ক্লি 'র পরিমাপ সমস্যা হল (বহুমাত্রিক) আয়তক্ষেত্রাকার পরিসরের মিলনের পরিমাপ কতটা দক্ষতার সাথে গণনা করা যেতে পারে তা নির্ধারণ করার সমস্যা। এখানে, একটি ডি-মাত্রিক আয়তক্ষেত্রাকার পরিসীমা বাস্তব সংখ্যার ডি ব্যবধানের একটি কার্টেসিয়ান গুণফল হিসাবে সংজ্ঞায়িত করা হয়, যা আরডির একটি উপসেট। সমস্যাটির নামকরণ করা হয়েছে ভিক্টর ক্লির নামে, যিনি ব্যবধানের মিলনের দৈর্ঘ্য গণনা করার জন্য একটি অ্যালগরিদম দিয়েছিলেন (কেস ডি = 1) যা পরে গণনামূলক জটিলতা তত্ত্বের অর্থে সর্বোত্তমভাবে দক্ষ বলে প্রমাণিত হয়েছিল। দ্বিমাত্রিক আয়তক্ষেত্রাকার পরিসরের মিলনের ক্ষেত্র গণনা করার গণনামূলক জটিলতাও এখন জানা যায়, তবে d ± 3 ক্ষেত্রে একটি উন্মুক্ত সমস্যা রয়ে গেছে। ইতিহাস এবং অ্যালগরিদম 1977 সালে, ভিক্টর ক্লি নিম্নলিখিত সমস্যাটি বিবেচনা করেছিলেনঃ বাস্তব লাইনে n ব্যবধানের একটি সংগ্রহ দেওয়া হলে, তাদের মিলনের দৈর্ঘ্য গণনা করুন। তারপরে তিনি গণনামূলক জটিলতা (বা "চলমান সময়") দিয়ে এই সমস্যা সমাধানের জন্য একটি অ্যালগরিদম উপস্থাপন করেন-এই বিবৃতির অর্থের জন্য বিগ ও নোটেশন দেখুন। ব্যবধানগুলি সাজানোর উপর ভিত্তি করে এই অ্যালগরিদমটি পরে মাইকেল ফ্রেডম্যান এবং ব্রুস ওয়েইড (1978) দ্বারা সর্বোত্তম বলে দেখানো হয়েছিল। পরে 1977 সালে, জন বেন্টলি এই সমস্যার একটি দ্বিমাত্রিক সাদৃশ্য বিবেচনা করেছিলেনঃ n আয়তক্ষেত্রের একটি সংগ্রহ দেওয়া হলে, তাদের মিলনের ক্ষেত্রটি খুঁজে বের করুন। তিনি একটি জটিলতা অ্যালগরিদমও পেয়েছিলেন, যা এখন বেন্টলির অ্যালগরিদম নামে পরিচিত, যা সমস্যাটিকে এন-1-মাত্রিক সমস্যায় হ্রাস করার উপর ভিত্তি করেঃ এটি এলাকা জুড়ে একটি উল্লম্ব রেখা ছড়িয়ে দিয়ে করা হয়। এই পদ্ধতি ব্যবহার করে, ইউনিয়নের ক্ষেত্রটি স্পষ্টভাবে ইউনিয়নটি তৈরি না করেই গণনা করা যেতে পারে। বেন্টলির অ্যালগরিদম এখন সর্বোত্তম (দ্বিমাত্রিক ক্ষেত্রে) হিসাবেও পরিচিত, এবং অন্যান্য ক্ষেত্রের মধ্যে কম্পিউটার গ্রাফিক্সে ব্যবহৃত হয়। এই দুটি সমস্যা হল আরও সাধারণ প্রশ্নের 1-এবং 2-মাত্রিক কেসঃ nd-মাত্রিক আয়তক্ষেত্রাকার পরিসরের একটি সংগ্রহ দেওয়া হলে, তাদের মিলনের পরিমাপ গণনা করুন। এই সাধারণ সমস্যাটি হল ক্লির পরিমাপের সমস্যা। যখন ডি-ডাইমেনশনাল ক্ষেত্রে সাধারণীকরণ করা হয়, তখন বেন্টলির অ্যালগরিদমের একটি চলমান সময় থাকে। এটি সর্বোত্তম বলে প্রমাণিত হয় না, কারণ এটি শুধুমাত্র ডি-মাত্রিক সমস্যাটিকে এন (ডি-1)-মাত্রিক সমস্যায় বিভক্ত করে এবং সেই উপ-সমস্যাগুলিকে আরও বিচ্ছিন্ন করে না। 1981 সালে, জ্যান ভ্যান লিউয়েন এবং ডেরেক উড ডাইনামিক কোয়াডট্রি ব্যবহার করে এই অ্যালগরিদমের চলমান সময়কে ডি ≤ 3-এ উন্নত করেন। 1988 সালে, মার্ক ওভারমারস এবং চি ইয়াপ ডিওআর 3-এর জন্য একটি অ্যালগরিদম প্রস্তাব করেছিলেন। তাদের অ্যালগরিদম একটি কে. ডি-ট্রি-র মতো একটি নির্দিষ্ট তথ্য কাঠামো ব্যবহার করে সমস্যাটিকে দ্বিমাত্রিক উপাদানগুলিতে বিভক্ত করে এবং সেই উপাদানগুলিকে দক্ষতার সাথে একত্রিত করে; দ্বিমাত্রিক সমস্যাগুলি নিজেই একটি ট্রেলিস কাঠামো ব্যবহার করে দক্ষতার সাথে সমাধান করা হয়। যদিও বেন্টলির অ্যালগরিদমের তুলনায় অ্যাসিম্পটোটিকভাবে দ্রুত, এর ডেটা স্ট্রাকচারগুলি উল্লেখযোগ্যভাবে বেশি স্থান ব্যবহার করে, তাই এটি কেবল সেই সমস্যাগুলিতে ব্যবহৃত হয় যেখানে এন বা ডি বড়। 1998 সালে, বোগদান ক্লেবাস সাধারণ বিশেষ ক্ষেত্রে যেখানে ডি 3 বা 4 হয় তার জন্য একই অ্যাসিম্পটোটিক চলমান সময়ের সাথে একটি সহজ অ্যালগরিদম প্রস্তাব করেছিলেন। 2013 সালে, টিমোথি এম. চ্যান একটি সহজতর অ্যালগরিদম তৈরি করেছিলেন যা গতিশীল তথ্য কাঠামোর প্রয়োজনীয়তা এড়ায় এবং লগারিদমিক ফ্যাক্টরকে সরিয়ে দেয়, যা ডি ≤ 3-এর জন্য সর্বাধিক পরিচিত চলমান সময়কে কমিয়ে দেয়। জ্ঞাত সীমা যে কোনও ডি-এর জন্য একমাত্র জ্ঞাত নিম্ন সীমা হল, এবং এই চলমান সময়ের সাথে সর্বোত্তম অ্যালগরিদমগুলি ডি = 1 এবং ডি = 2-এর জন্য পরিচিত। চ্যান অ্যালগরিদম d ≤ 3-এর জন্য একটি ঊর্ধ্বসীমা প্রদান করে, তাই d ≤ 3-এর জন্য, এটি একটি উন্মুক্ত প্রশ্ন রয়ে গেছে যে দ্রুততর অ্যালগরিদম সম্ভব কিনা, অথবা বিকল্পভাবে আরও কঠোর নিম্নসীমা প্রমাণ করা যেতে পারে কিনা। বিশেষত, অ্যালগরিদমের চলমান সময় অবশ্যই ডি-এর উপর নির্ভর করবে কিনা তা উন্মুক্ত থাকে। উপরন্তু, বিশেষ ক্ষেত্রে (উদাহরণস্বরূপ, যখন ইনপুট স্থানাঙ্কগুলি একটি সীমাবদ্ধ সীমার মধ্যে পূর্ণসংখ্যা হয়) মোকাবেলা করতে পারে এমন দ্রুততর অ্যালগরিদম রয়েছে কিনা তা নিয়ে প্রশ্ন খোলা থাকে। 1ডি ক্লির পরিমাপ সমস্যা (ব্যবধানের মিলন) সমাধান করা যেতে পারে যেখানে পি সমস্ত ব্যবধানকে আঘাত করার জন্য প্রয়োজনীয় ছিদ্র বিন্দুর সংখ্যা বোঝায় (একটি সাধারণ বিন্দু দ্বারা ছিদ্র করা ব্যবধানের মিলনটি চরম গণনা করে রৈখিক সময়ে গণনা করা যেতে পারে)। প্যারামিটার পি একটি অভিযোজিত প্যারামিটার যা ইনপুট কনফিগারেশনের উপর নির্ভর করে এবং ভেদন অ্যালগরিদম ক্লি 'র পরিমাপ সমস্যার জন্য একটি অভিযোজিত অ্যালগরিদম প্রদান করে। আরও দেখুন কনভেক্স আয়তনের আনুমানিক হিসাব, যা উত্তল বস্তুর জন্য একটি দক্ষ অ্যালগরিদম। । । । । । । মাধ্যমিক সাহিত্য ফ্রাঙ্কো পি. প্রিপারেটা এবং মাইকেল আই. শামোস (1985)। গণনামূলক জ্যামিতি (স্প্রিঙ্গার-ভার্লাগ, বার্লিন)। ক্লির পরিমাপ সমস্যা, অধ্যাপক জেফ এরিকসনের গণনামূলক জ্যামিতিতে উন্মুক্ত সমস্যার তালিকা থেকে। (অ্যাক্সেস করা হয়েছে নভেম্বর 8,2005, যখন শেষ আপডেটটি ছিল জুলাই 31,1998।) তথ্যসূত্র গণনামূলক জ্যামিতি পরিমাপ তত্ত্ব গাণিতিক সমস্যা