Kinetic convex hull
حرکی کنویکس ہل ڈیٹا ڈھانچہ ایک حرکی ڈیٹا ڈھانچہ ہے جو مسلسل حرکت پذیر پوائنٹس کے سیٹ کے کنویکس ہل کو برقرار رکھتا ہے۔ اسے متحرک کنویکس ہل ڈیٹا ڈھانچوں سے ممتاز کیا جانا چاہیے، جو مسلسل حرکت کے بجائے پوائنٹس کے اندراج یا حذف کرنے جیسی مجرد تبدیلیوں سے گزرنے والے پوائنٹس کو سنبھالتے ہیں۔ 2 ڈی کیس 2 جہتی متحرک کنویکس ہل کے مسئلے کے لیے سب سے مشہور ڈیٹا ڈھانچہ باسچ، گیباس اور ہرشبرگر کا ہے۔ یہ ڈیٹا ڈھانچہ ذمہ دار، موثر، کمپیکٹ اور مقامی ہے۔ اعداد و شمار کا ڈھانچہ پوائنٹس کے ایک سیٹ کے کنویکس ہل کا ڈوئل لائنوں کے ڈوئل سیٹ کے اوپری اور نچلے لفافے ہوتے ہیں۔ لہذا، حرکت پذیر لائنوں کے سیٹ کے اوپری اور نچلے لفافوں کو برقرار رکھنا حرکت پذیر پوائنٹس کے سیٹ کے کنویکس ہل کو برقرار رکھنے کے مترادف ہے۔ اوپری اور نچلے لفافوں کی کمپیوٹنگ مساوی مسائل ہیں، لہذا لائنوں کے سیٹ کے اوپری لفافے کی کمپیوٹنگ حرکت پذیر پوائنٹس کے سیٹ کے کنویکس ہل کی کمپیوٹنگ کے برابر ہے۔ جامد لائنوں کے سیٹ کے اوپری لفافے کو تقسیم اور فتح الگورتھم کا استعمال کرتے ہوئے شمار کیا جا سکتا ہے جو لائنوں کو مساوی سائز کے دو سیٹوں میں تقسیم کرتا ہے، اپنے اوپری لفافوں کو تلاش کرنے کے لیے خود کو دونوں سیٹوں پر بار بار کال کرتا ہے، اور پھر دونوں کے نتیجے میں اوپری لفافوں کو ضم کرتا ہے۔ انضمام کا مرحلہ عمودی لائن سویپ کا استعمال کرتے ہوئے انجام دیا جاتا ہے۔ پوائنٹس کے پہلے سیٹ کو نیلا اور پوائنٹس کے دوسرے سیٹ کو سرخ کال کریں۔ اوپری لفافوں کو ضم کرنے کے لیے معیاری لائن سویپ الگورتھم بائیں سے دائیں سرخ اور نیلے اوپری لفافوں کے تمام عمودی حصوں کو جھاڑتا ہے۔ سب سے حال ہی میں سامنے آنے والے سرخ اور نیلے پوائنٹس کو لائن سویپ کے طور پر برقرار رکھا جاتا ہے۔ جب کسی نقطہ کا سامنا کرنا پڑتا ہے، تو الگورتھم چیک کرتا ہے کہ آیا نقطہ مخالف رنگ کے آخری نقطہ کے بعد حصے کے اوپر یا نیچے ہے۔ اگر یہ اوپر ہے، تو اس نقطہ کو ضم شدہ اوپری لفافے میں شامل کیا جاتا ہے۔ اگر یہ آخری اضافی پوائنٹ سے مختلف رنگ کا ہے، تو سرخ اور نیلے لفافے پار ہو چکے ہیں، اس لیے انٹرسیکشن پوائنٹ کو بھی ضم شدہ اوپری لفافے میں شامل کیا جاتا ہے۔ اس الگورتھم کے نتیجے میں کناروں اور عمودی حصوں کی ترتیب صرف پوائنٹس کی ترتیب، اور لائن پوائنٹ موازنہ کے نتائج پر منحصر ہے۔ اس طرح، نتیجہ کو درج ذیل سرٹیفکیٹ کے ساتھ تصدیق شدہ کیا جا سکتا ہے: ایکس سرٹیفکیٹ () کا استعمال سرخ اور نیلے لفافوں کے عمودی ترتیب کی تصدیق کے لیے کیا جاتا ہے۔ وہ عمودی سیٹ پر متحرک ترتیب شدہ فہرست کے لیے سرٹیفکیٹ ہیں۔ چونکہ ہر پوائنٹ میں 2 لائنیں شامل ہیں، اور سرٹیفکیٹ میں 2 پوائنٹس شامل ہیں، اس لیے ہر سرٹیفکیٹ میں 4 لائنیں شامل ہیں۔ y-سرٹیفکیٹ () کا استعمال اس بات کی تصدیق کے لیے کیا جاتا ہے کہ ایک ورٹیکس کسی کنارے کے اوپر یا نیچے ہے۔ سرٹیفکیٹ ان تمام موازنہ کے لیے ظاہر ہوتے ہیں جو الگورتھم کے دوران ہوتے ہیں۔ جب تک یہ تمام سرٹیفکیٹ برقرار رہیں گے، انضمام کے مراحل کو یکساں طور پر انجام دیا جائے گا، لہذا اس کے نتیجے میں اوپری لفافے ایک جیسے ہوں گے۔ اوپری لفافوں کے لیے متحرک ڈیٹا ڈھانچہ ان سرٹیفکیٹس کا استعمال کرتے ہوئے جامد اوپری لفافے کے الگورتھم کی تصدیق کے لیے بنایا جا سکتا ہے۔ تاہم، یہ اسکیم مقامی نہیں ہے، کیونکہ ایک لائن بہت سے Y-سرٹیفکیٹ میں شامل ہوتی ہے اگر یہ اوپر یا نیچے رہتی ہے جیسا کہ دوسرے لفافے سے کئی نکات کا سامنا ہوتا ہے۔ اس طرح، ایک ایس-سرٹیفکیٹ () متعارف کرانا ضروری ہے جو اس بات کی تصدیق کرتا ہے کہ کسی لکیر کی ڈھلوان دوسری لکیر کی ڈھلوان سے زیادہ یا کم ہے۔ تمام پوائنٹس اے بی کے لیے درج ذیل سرٹیفکیٹ کا ہونا انضمام کے نتیجے میں کناروں اور عمودی حصوں کی ترتیب کی تصدیق کے لیے کافی ہے، فی لائن صرف او (1) سرٹیفکیٹ کے ساتھ:: اس کی دائیں طرف کے قریب ترین سرے کی نشاندہی کرتا ہے۔ یہ سرٹیفکیٹ ان تمام پوائنٹس کے لیے محفوظ کیا جاتا ہے جن کا رنگ پوائنٹ سے مختلف ہوتا ہے، جو ان کے بعد آتا ہے۔ : یا۔ یہ سرٹیفکیٹ ان تمام نکات کے لیے محفوظ کیا جاتا ہے جو ایک دوسرے کو کاٹتے ہیں۔ دوسرے لفافے کے کنارے کے مدمقابل کنارے کی نشاندہی کرتا ہے جو اوپر یا نیچے ہے۔ : یا۔ یہ سرٹیفکیٹ ان تمام نکات کے لیے محفوظ کیا جاتا ہے جو ایک دوسرے کو کاٹتے ہیں۔ :۔ یہ سرٹیفکیٹ ان تمام پوائنٹس کے لیے محفوظ کیا جاتا ہے جن کے لیے اور۔ :۔ یہ سرٹیفکیٹ ان تمام پوائنٹس کے لیے محفوظ کیا جاتا ہے جن کے لیے اور۔ :۔ یہ سرٹیفکیٹ ان تمام پوائنٹس کے لیے محفوظ کیا جاتا ہے جن کے لیے اور۔ :۔ یہ سرٹیفکیٹ ان تمام پوائنٹس کے لیے محفوظ کیا جاتا ہے جن کے لیے اور۔ :۔ یہ سرٹیفکیٹ ان تمام پوائنٹس کے لیے محفوظ کیا جاتا ہے جن کے لیے اور۔ پہلا سرٹیفکیٹ، سرخ اور نیلے لفافوں میں پوائنٹس کے ایکس آرڈر کی تصدیق کرتا ہے۔ دوسرے اور تیسرے سرٹیفکیٹ، اور، سرخ اور نیلے لفافوں کے چوراہوں کی تصدیق کرتے ہیں۔ باقی 5 سرٹیفکیٹ،،،،، اور ایسے کناروں کو رکھیں جو اوپری لفافوں میں نہیں ہیں ان کناروں کی ڈھلوانوں کی ترتیب میں جو اس کے اوپر ہیں۔ اگر ڈھلوان ترتیب کے آغاز یا اختتام پر ہے، یا اس کی تصدیق کریں۔ اگر یہ ترتیب کے وسط میں ہے، اور اس کی تصدیق کرتا ہے، اور تصدیق کرتا ہے کہ دونوں لائنوں کا انٹرسیکشن پوائنٹ کہ کنارے کی ڈھلوان درمیان میں ہے، اس کے اوپر ہے۔ یہ ایک یا تین سرٹیفکیٹ یہ ثابت کرنے کے لیے کافی ہیں کہ تمام کنارے اس لکیر کے اوپر ہیں۔ پچھلی اسکیم کے برعکس تمام لائنیں صرف مستقل تعداد میں سرٹیفکیٹ میں شامل ہوتی ہیں۔ جب بھی ان میں سے سرٹیفکیٹ ناکام ہوتے ہیں، تو ضم شدہ لفافے اور سرٹیفکیٹ کو او (1) وقت میں اپ ڈیٹ کیا جا سکتا ہے۔ کنویکس ہل کے لیے حرکی ڈیٹا ڈھانچہ ان سرٹیفکیٹ کا استعمال کرتے ہوئے تعمیر کیا جاتا ہے تاکہ اوپری لفافوں کے تکراری انضمام کی تصدیق کی جا سکے۔ جب بھی سرٹیفکیٹ ناکام ہوتے ہیں، ان کے انضمام کو اپ ڈیٹ کیا جاتا ہے، اور اگر انضمام کے نتیجے میں لفافے میں تبدیلی آتی ہے، تو تبدیلیوں کو ان تمام انضمام کے ذریعے پھیلایا جاتا ہے جو انضمام کے نتیجے پر منحصر ہوتے ہیں۔ کارکردگی یہ ڈیٹا ڈھانچہ ذمہ دار، مقامی، کمپیکٹ اور موثر ہے۔ یہ اوپری لفافے کی تصدیق کے لیے استعمال ہونے والے انضمام کی لوگرتھمک گہرائی کی وجہ سے ہے۔ ذمہ دار: جب کوئی سرٹیفکیٹ ناکام ہوجاتا ہے، تو اس کے تصدیق شدہ انضمام کو ٹھیک کرنے میں O (1) لگتا ہے۔ اگر نتیجے میں لفافے میں تبدیلی آتی ہے، تو تبدیلی کو تمام انضمام تک پھیلانا ضروری ہے جو تبدیل شدہ انضمام کے نتیجے پر منحصر ہے۔ اس طرح کے انضمام او (لاگ این) ہیں، لہذا اپ ڈیٹ کو کل او (لاگ این) ٹائم میں انجام دیا جا سکتا ہے۔ مقامی: ہر لائن زیادہ سے زیادہ او (لاگ این) سرٹیفکیٹ میں شامل ہوتی ہے۔ اس کی وجہ یہ ہے کہ ہر لائن ہر انضمام میں سرٹیفکیٹ کی مستقل تعداد میں شامل ہوتی ہے، اور ہر لائن O (لاگ n) میں ہوتی ہے جو کل ضم ہوتی ہے۔ کمپیکٹنیس: اس ڈیٹا ڈھانچے میں استعمال ہونے والے سرٹیفکیٹ کی زیادہ سے زیادہ تعداد O (n لاگ n) ہے۔ اس کی وجہ یہ ہے کہ ہر انضمام میں متعدد سرٹیفکیٹ شامل ہوتے ہیں جو ضم شدہ لائنوں کی تعداد سے لکیری ہوتے ہیں۔ این لائنوں کے اوپری لفافے کی تصدیق کے لیے این/2 لائنوں کے دو ذیلی سیٹوں کے ضم شدہ اوپری لفافے کے لیے سرٹیفکیٹ اور لفافوں کے انضمام کے لیے سرٹیفکیٹ درکار ہوتے ہیں۔ اس طرح سرٹیفکیٹ کی تعداد، C (n)، جو کہ n لائنوں کے اوپری لفافے کی تصدیق کے لیے درکار ہوتی ہے، C (1) = O (1) کے ساتھ تکرار C (n) = 2C (n/2) + O (n) کو مطمئن کرتی ہے۔ تقسیم اور فتح کے تکرار کے ماسٹر تھیوریم کے مطابق، C (n) = O (n log n)۔ کارکردگی: الجبرائی یا فرضی الجبرائی راستوں پر اس الگورتھم کے ذریعے عمل کیے جانے والے واقعات کی زیادہ سے زیادہ تعداد، سب کے لیے، کواڈریٹک کے قریب ہے۔ لکیری طور پر حرکت پذیر پوائنٹس کے کنویکس ہلز وقت تبدیل کر سکتے ہیں۔ اس طرح یہ ڈیٹا ڈھانچہ موثر ہے۔ اعلی طول و عرض 2 سے زیادہ طول و عرض میں حرکت پذیر پوائنٹس کے کنویکس ہل کو برقرار رکھنے کے لیے ایک موثر حرکی ڈیٹا ڈھانچہ تلاش کرنا ایک کھلا مسئلہ ہے۔ متعلقہ مسائل حرکی کنویکس ہل کو درج ذیل متعلقہ مسائل کو حل کرنے کے لیے استعمال کیا جا سکتا ہے: حرکی قطر حرکی چوڑائی حرکی کم از کم باکس حرکی سب سے چھوٹی منسلک ڈسک حوالہ جات حرکی ڈیٹا ڈھانچے کنویکس ہل الگورتھم