Zone theorem
جیومیٹری میں، زون تھیوریم ایک ایسا نتیجہ ہے جو لائنوں کی ترتیب میں لائن کے زون کی پیچیدگی کو قائم کرتا ہے۔ تعریف ایک لکیر کی ترتیب، جسے اس کے طور پر ظاہر کیا جاتا ہے، طیارہ کی ایک ذیلی تقسیم ہے، جو لکیروں کے ایک سیٹ سے خلیوں (جہتی چہروں)، کناروں (جہتی چہروں) اور عمودی (جہتی چہروں) میں متاثر ہوتی ہے۔ لکیروں کے ایک سیٹ، لکیر کے ترتیب، اور ایک لکیر (جس سے تعلق نہیں ہے) کو دیکھتے ہوئے، کا زون ان چہروں کا مجموعہ ہے جو ایک دوسرے سے جڑے ہوئے ہیں۔ کسی زون کی پیچیدگی اس کی حدود میں کناروں کی کل تعداد ہے، جس کا اظہار فنکشن کے طور پر کیا جاتا ہے۔ زون تھیوریم بیان کرتا ہے کہ کہا گیا پیچیدگی ہے۔ یہ نتیجہ پہلی بار 1985 میں شائع ہوا۔ Chazelle et al. ایک ترتیب میں لائن کے زون کی پیچیدگی کے لیے کی اوپری حد دی گئی۔ 1991 میں، اس باؤنڈ کو بہتر بنایا گیا، اور یہ بھی دکھایا گیا کہ یہ ایک چھوٹے اضافی عنصر تک بہترین ممکنہ اوپری باؤنڈ ہے۔ پھر، 2011 میں، روم پنچاسی نے ثابت کیا کہ ایک ترتیب میں لائن کے زون کی پیچیدگی زیادہ سے زیادہ ہے، اور یہ ایک سخت باؤنڈ ہے۔ تھیوریم کے مختلف ثبوتوں میں استعمال ہونے والے کچھ نمونے انڈکشن، سویپ تکنیک، درخت کی تعمیر، اور ڈیوینپورٹ-شنزل ترتیبات ہیں۔ عامیاں اگرچہ سب سے زیادہ مقبول ورژن طیارہ میں لائنوں کے انتظامات کے لیے ہے، لیکن زون تھیوریم کی کچھ عامیاں موجود ہیں۔ مثال کے طور پر، طول و عرض میں، ہائپرپلین کے انتظامات پر غور کرتے ہوئے، ہائپرپلین کے زون کی پیچیدگی خلیوں کے سیٹ (-جہتی چہروں) سے جڑے پہلوؤں (-جہتی چہروں) کی تعداد ہے۔ اسی طرح،-جہتی زون تھیوریم بیان کرتا ہے کہ ہائپرپلین کے زون کی پیچیدگی ہے۔ طول و عرض کے نظریہ کے لیے کافی کم ثبوت موجود ہیں۔ جہتی معاملے کے لیے، سویپ تکنیک پر مبنی ثبوت موجود ہیں اور اعلی جہتوں کے لیے اویلر کا تعلق استعمال کیا جاتا ہے: ایک اور عمومی شکل لائنوں (اور ہائپرپلین) کے بجائے سڈوولینز (اور طول و عرض میں سڈو ہائپرپلین) کے انتظامات پر غور کرنا ہے۔ تھیوریم کے کچھ ثبوت اس معاملے میں اچھی طرح سے کام کرتے ہیں کیونکہ وہ اپنے دلائل کے ذریعے لائنوں کی سیدھی پن کو کافی حد تک استعمال نہیں کرتے ہیں۔ محرک انتظامات میں زون کی پیچیدگی کا مطالعہ کرنے کا بنیادی محرک انتظامات کی تعمیر کے لیے موثر الگورتھم کی تلاش سے پیدا ہوتا ہے۔ کلاسیکی الگورتھم انکریمنٹل کنسٹرکشن ہے، جسے تقریبا ایک کے بعد ایک لائنوں کو شامل کرنے اور ہر ایک کے ذریعہ تیار کردہ تمام چہروں کو مناسب ڈیٹا ڈھانچے میں محفوظ کرنے کے طور پر بیان کیا جا سکتا ہے (انتظامات کے لیے معمول کا ڈھانچہ ڈبل کنیکٹڈ ایج لسٹ (ڈی سی ای ایل) ہے)۔ یہاں، زون تھیوریم کا نتیجہ یہ ہے کہ لائنوں کے کسی بھی ترتیب کی پوری تعمیر وقت پر کی جا سکتی ہے، کیونکہ ہر لائن کے داخل ہونے میں وقت لگتا ہے۔ حوالہ جات نوٹ کریں۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ طیارہ جیومیٹری میں یوکلڈین طیارہ جیومیٹری تھیوریم