Klee's measure problem
کمپیوٹیشنل جیومیٹری میں، کلی کا پیمائش کا مسئلہ اس بات کا تعین کرنے کا مسئلہ ہے کہ (کثیر جہتی) آئتاکار حدود کے اتحاد کی پیمائش کا حساب کس حد تک مؤثر طریقے سے لگایا جا سکتا ہے۔ یہاں، ایک ڈی جہتی آئتاکار رینج کو حقیقی اعداد کے ڈی وقفوں کے کارٹیشین پروڈکٹ کے طور پر بیان کیا گیا ہے، جو کہ Rd کا ذیلی مجموعہ ہے۔ اس مسئلے کا نام وکٹر کلی کے نام پر رکھا گیا ہے، جس نے وقفوں کے اتحاد کی لمبائی کا حساب لگانے کے لیے ایک الگورتھم دیا (کیس d = 1) جسے بعد میں کمپیوٹیشنل پیچیدگی کے نظریہ کے لحاظ سے بہتر طور پر موثر دکھایا گیا۔ 2 جہتی آئتاکار حدود کے اتحاد کے رقبے کی کمپیوٹنگ کی کمپیوٹیشنل پیچیدگی اب بھی معلوم ہے، لیکن معاملہ d ≤ 3 ایک کھلا مسئلہ ہے۔ تاریخ اور الگورتھم 1977 میں، وکٹر کلی نے مندرجہ ذیل مسئلے پر غور کیا: حقیقی لکیر میں n وقفوں کے مجموعے کو دیکھتے ہوئے، ان کے اتحاد کی لمبائی کا حساب لگائیں۔ اس کے بعد انہوں نے کمپیوٹیشنل پیچیدگی (یا "رننگ ٹائم") کے ساتھ اس مسئلے کو حل کرنے کے لیے ایک الگورتھم پیش کیا-اس بیان کے معنی کے لیے بگ او نوٹیشن دیکھیں۔ وقفوں کو ترتیب دینے پر مبنی اس الگورتھم کو بعد میں مائیکل فریڈمین اور بروس ویڈ (1978) نے بہترین دکھایا۔ بعد میں 1977 میں، جون بینٹلے نے اس مسئلے کے دو جہتی ینالاگ پر غور کیا: n مستطیلوں کے مجموعے کو دیکھتے ہوئے، ان کے اتحاد کا رقبہ تلاش کریں۔ اس نے ایک پیچیدگی الگورتھم بھی حاصل کیا، جسے اب بینٹلے کے الگورتھم کے نام سے جانا جاتا ہے، جو مسئلے کو n 1 جہتی مسائل تک کم کرنے پر مبنی ہے: یہ پورے علاقے میں عمودی لکیر کو جھاڑ کر کیا جاتا ہے۔ اس طریقہ کار کا استعمال کرتے ہوئے، یونین کے رقبے کا حساب واضح طور پر یونین کی تعمیر کے بغیر کیا جا سکتا ہے۔ Bentley کا الگورتھم اب زیادہ سے زیادہ (2 جہتی معاملے میں) بھی جانا جاتا ہے، اور دوسرے شعبوں کے علاوہ کمپیوٹر گرافکس میں استعمال ہوتا ہے۔ یہ دو مسائل زیادہ عام سوال کے 1-اور 2-جہتی معاملات ہیں: n-d-جہتی آئتاکار حدود کے مجموعے کو دیکھتے ہوئے، ان کے اتحاد کی پیمائش کا حساب لگائیں۔ یہ عمومی مسئلہ کلی کی پیمائش کا مسئلہ ہے۔ جب D-جہتی کیس کو عام کیا جاتا ہے، تو Bentley کے الگورتھم کا رننگ ٹائم ہوتا ہے۔ یہ بہتر ثابت نہیں ہوتا ہے، کیونکہ یہ صرف ڈی جہتی مسئلے کو این (ڈی-1) جہتی مسائل میں تحلیل کرتا ہے، اور ان ذیلی مسائل کو مزید تحلیل نہیں کرتا ہے۔ 1981 میں، جان وین لیوین اور ڈیرک ووڈ نے متحرک کواڈٹریز کا استعمال کرتے ہوئے اس الگورتھم کے چلانے کے وقت کو بہتر بنا کر ڈی ≤ 3 کر دیا۔ 1988 میں مارک اوورمارس اور چی یاپ نے ڈی ≤ 3 کے لیے ایک الگورتھم تجویز کیا۔ ان کا الگورتھم مسئلہ کو 2 جہتی اجزاء میں تحلیل کرنے اور ان اجزاء کو مؤثر طریقے سے جمع کرنے کے لیے کے ڈی ٹری کی طرح ایک مخصوص ڈیٹا ڈھانچے کا استعمال کرتا ہے۔ 2 جہتی مسائل خود ایک ٹریلس ڈھانچے کا استعمال کرتے ہوئے مؤثر طریقے سے حل کیے جاتے ہیں۔ اگرچہ بینٹلے کے الگورتھم سے غیر علامتی طور پر تیز، اس کے ڈیٹا ڈھانچے نمایاں طور پر زیادہ جگہ استعمال کرتے ہیں، لہذا یہ صرف ان مسائل میں استعمال ہوتا ہے جہاں n یا d بڑا ہوتا ہے۔ 1998 میں، بوگڈن کلیبس نے عام خصوصی معاملات کے لیے ایک ہی ایسمپٹوٹک رننگ ٹائم کے ساتھ ایک آسان الگورتھم کی تجویز پیش کی جہاں d 3 یا 4 ہے۔ 2013 میں، ٹموتھی ایم چن نے ایک آسان الگورتھم تیار کیا جو متحرک ڈیٹا ڈھانچے کی ضرورت سے بچتا ہے اور لوگرتھمک عنصر کو ختم کرتا ہے، جس سے 3 سے 3 کے لیے سب سے مشہور رننگ ٹائم کم ہو جاتا ہے۔ معلوم حدود کسی بھی ڈی کے لیے واحد معلوم نچلی حد ہے، اور اس رننگ ٹائم کے ساتھ زیادہ سے زیادہ الگورتھم ڈی = 1 اور ڈی = 2 کے لیے جانے جاتے ہیں۔ چن الگورتھم d ≤ 3 کے لیے ایک اوپری حد فراہم کرتا ہے، لہذا d ≤ 3 کے لیے، یہ ایک کھلا سوال رہتا ہے کہ کیا تیز الگورتھم ممکن ہیں، یا متبادل طور پر کیا سخت نچلی حدود کو ثابت کیا جا سکتا ہے۔ خاص طور پر، یہ کھلا رہتا ہے کہ آیا الگورتھم کے چلنے کا وقت ڈی پر منحصر ہونا چاہیے۔ اس کے علاوہ، یہ سوال کھلا رہتا ہے کہ آیا تیز تر الگورتھم ہیں جو خصوصی معاملات سے نمٹ سکتے ہیں (مثال کے طور پر، جب ان پٹ کوآرڈینیٹ ایک باؤنڈ رینج کے اندر انٹیجر ہوتے ہیں)۔ 1 ڈی کلی کا پیمائش کا مسئلہ (وقفوں کا اتحاد) حل کیا جا سکتا ہے جہاں p تمام وقفوں کو چھیدنے کے لیے درکار چھیدنے والے پوائنٹس کی تعداد کو ظاہر کرتا ہے (ایک مشترکہ نقطہ سے چھیدے گئے وقفوں کا اتحاد لکیری وقت میں انتہا کا حساب لگا کر شمار کیا جا سکتا ہے)۔ پیرامیٹر پی ایک انکولی پیرامیٹر ہے جو ان پٹ ترتیب پر منحصر ہے، اور چھیدنے والا الگورتھم کلی کے پیمائش کے مسئلے کے لیے ایک انکولی الگورتھم فراہم کرتا ہے۔ کنویکس حجم کا تخمینہ، کنویکس باڈیز کے لیے ایک موثر الگورتھم حوالہ جات اور مزید اہم مقالے پڑھنا بھی دیکھیں۔ ۔ ۔ ۔ ۔ ۔ ۔ ثانوی ادب فرانکو پی پریپراٹا اور مائیکل آئی شاموس (1985)۔ کمپیوٹیشنل جیومیٹری (سپرنگر-ورلاگ، برلن)۔ کلی کا پیمائش کا مسئلہ، پروفیسر جیف ایرکسن کی کمپیوٹیشنل جیومیٹری میں کھلے مسائل کی فہرست سے۔ (8 نومبر 2005 تک رسائی حاصل کی گئی، جب آخری اپ ڈیٹ 31 جولائی 1998 تھی۔) حوالہ جات کمپیوٹیشنل جیومیٹری پیمائش نظریہ ریاضیاتی مسائل