Zone theorem
জ্যামিতিতে, জোন উপপাদ্য হল এমন একটি ফলাফল যা রেখার বিন্যাসে একটি রেখার অঞ্চলের জটিলতা প্রতিষ্ঠা করে। সংজ্ঞা একটি রেখা বিন্যাস, যা হিসাবে চিহ্নিত করা হয়, সমতলের একটি উপবিভাগ, যা কোষ (-মাত্রিক মুখ), প্রান্ত (-মাত্রিক মুখ) এবং শীর্ষে (-মাত্রিক মুখ) রেখার একটি সেট দ্বারা প্ররোচিত হয়। রেখার একটি সেট, রেখা বিন্যাস এবং একটি রেখা (এর অন্তর্গত নয়) দেওয়া হলে, এর অঞ্চলটি দ্বারা ছেদ করা মুখগুলির সেট। একটি অঞ্চলের জটিলতা হল তার সীমানায় মোট প্রান্তের সংখ্যা, যা এর একটি ফাংশন হিসাবে প্রকাশ করা হয়। জোন উপপাদ্যটি বলে যে জটিলতা হল। ইতিহাস এই ফলাফলটি 1985 সালে প্রথম প্রকাশিত হয়েছিল; Chazelle et al। একটি বিন্যাসে একটি রেখার অঞ্চলের জটিলতার জন্য এর উপরের সীমা দেওয়া হয়েছে। 1991 সালে, এই সীমাটি উন্নত করা হয়েছিল, এবং এটিও দেখানো হয়েছিল যে এটি একটি ছোট অ্যাডিটিভ ফ্যাক্টর পর্যন্ত সর্বোত্তম সম্ভাব্য উপরের সীমা। তারপর, 2011 সালে, রম পিঞ্চাসি প্রমাণ করেন যে একটি বিন্যাসে একটি রেখার অঞ্চলের জটিলতা সর্বাধিক, এবং এটি একটি টাইট বাউন্ড। উপপাদ্যটির বিভিন্ন প্রমাণগুলিতে ব্যবহৃত কিছু দৃষ্টান্ত হল ইন্ডাকশন, সুইপ টেকনিক, ট্রি কনস্ট্রাকশন এবং ডেভেনপোর্ট-শচিনজেল সিকোয়েন্স। সাধারণীকরণ যদিও সর্বাধিক জনপ্রিয় সংস্করণটি সমতলে রেখার বিন্যাসের জন্য, তবে জোন উপপাদ্যের কিছু সাধারণীকরণ রয়েছে। উদাহরণস্বরূপ, মাত্রায়, হাইপারপ্লেনের বিন্যাস বিবেচনা করে, একটি হাইপারপ্লেনের অঞ্চলের জটিলতা হল কোষের সেট (-মাত্রিক মুখ) দ্বারা ছেদিত দিকগুলির সংখ্যা (-মাত্রিক মুখ)। অনুরূপভাবে,-মাত্রিক অঞ্চল উপপাদ্যটি বলে যে একটি হাইপারপ্লেনের অঞ্চলের জটিলতা হল। মাত্রার জন্য উপপাদ্যটির জন্য যথেষ্ট কম প্রমাণ রয়েছে। - মাত্রিক ক্ষেত্রে, সুইপ কৌশলের উপর ভিত্তি করে প্রমাণ রয়েছে এবং উচ্চতর মাত্রার জন্য অয়লারের সম্পর্ক ব্যবহার করা হয়ঃ আরেকটি সাধারণীকরণ হল রেখার (এবং হাইপারপ্লেন) পরিবর্তে সিউডোলিন (এবং মাত্রায় সিউডোহাইপারপ্লেন)-এর বিন্যাস বিবেচনা করা। উপপাদ্যটির জন্য কিছু প্রমাণ এই ক্ষেত্রে ভাল কাজ করে কারণ তারা তাদের যুক্তির মাধ্যমে রেখার সরলতা উল্লেখযোগ্যভাবে ব্যবহার করে না। অনুপ্রেরণা ব্যবস্থায় অঞ্চল জটিলতা অধ্যয়নের প্রাথমিক অনুপ্রেরণা ব্যবস্থা নির্মাণের জন্য দক্ষ অ্যালগরিদমের সন্ধান থেকে উদ্ভূত হয়। একটি ধ্রুপদী অ্যালগরিদম হল ক্রমবর্ধমান নির্মাণ, যা মোটামুটিভাবে একের পর এক লাইন যোগ করা এবং প্রতিটি দ্বারা উত্পন্ন সমস্ত মুখ একটি উপযুক্ত তথ্য কাঠামোতে সংরক্ষণ করা হিসাবে বর্ণনা করা যেতে পারে (ব্যবস্থার জন্য স্বাভাবিক কাঠামো হল দ্বিগুণ সংযুক্ত প্রান্ত তালিকা (ডিসিইএল))। এখানে, জোন উপপাদ্যের পরিণতি হল যে লাইনের যে কোনও বিন্যাসের সম্পূর্ণ নির্মাণ সময়মতো করা যেতে পারে, কারণ প্রতিটি লাইন সন্নিবেশ করতে সময় লাগে। উল্লেখগুলি উল্লেখ করুন। । । । । । । । । । ইউক্লিডীয় সমতলীয় জ্যামিতি সমতলীয় জ্যামিতিতে উপপাদ্য