Kinetic closest pair
ایک حرکی قریب ترین جوڑی ڈیٹا ڈھانچہ ایک حرکی ڈیٹا ڈھانچہ ہے جو قریب ترین جوڑی پوائنٹس کو برقرار رکھتا ہے، جس میں n پوائنٹس کا ایک سیٹ P دیا گیا ہے جو میٹرک اسپیس میں وقت کے ساتھ مسلسل حرکت کر رہے ہیں۔ اگرچہ جامد صورت میں بہت سے موثر الگورتھم معلوم تھے، لیکن ان کو متحرک کرنا مشکل ثابت ہوا، اس لیے اس مسئلے کو حل کرنے کے لیے نئے جامد الگورتھم تیار کیے گئے۔ 2 ڈی کیس اپروچ 1 قریب ترین جوڑے کی دیکھ بھال کے لیے سب سے آسان حرکی نقطہ نظر ڈیلونی مثلث کی مختلف شکلوں کا استعمال کرنا ہے۔ ایک مسدس پر غور کریں اور اسے چھ مساوی مثلثوں میں تقسیم کریں، اور پھر ہر مساوی مثلث کی بنیاد پر ایک ڈیلونی مثلث بنائیں، کیونکہ ہر ایک متغیر شکل کا ہے۔ ان چھ ڈیلونی مثلثوں کا اتحاد، جسے ایکوا لیٹرل ڈیلونی گراف (ای ڈی جی) کہا جاتا ہے، قریب ترین پڑوسی گراف (این این جی) کے لیے ایک سپر گراف ہے۔ ای ڈی جی میں کم سے کم لمبائی والے کنارے کے اختتامی نکات قریب ترین جوڑا دیتے ہیں۔ کنویکس شکلوں کی بنیاد پر ڈیلونی مثلث کو برقرار رکھنا سیدھا ہے۔ وقت کے ساتھ ای ڈی جی کو دیکھتے ہوئے، ای ڈی جی کے کناروں پر ایک متحرک ٹورنامنٹ ٹری بنا کر، کوئی بھی آسانی سے قریب ترین جوڑی کو برقرار رکھ سکتا ہے۔ یہ قریب ترین جوڑا کے ڈی ایس موثر، قابل جواب دہ اور کمپیکٹ ہے، لیکن عام طور پر مقامی نہیں ہے۔ مندرجہ ذیل نقطہ نظر قریب ترین جوڑے کی دیکھ بھال کے لیے مقامی کے ڈی ایس پیش کرتا ہے۔ نقطہ نظر 2 دوسرا حرکی نقطہ نظر درج ذیل مشاہدات پر مبنی ہے۔ تقسیم کریں اور فتح کریں اگر کسی نقطہ کے ارد گرد کی جگہ کو کونیی طور پر چھ "پٹریوں" میں تقسیم کیا جاتا ہے، ہر چوڑا، قریب ترین نقطہ ہر پٹری میں قریب ترین نقطہ کا قریب ترین ہوتا ہے۔ اس مضمون کا بقیہ حصہ "مرکزی" پٹریوں (جو ایکس محور سے بکھرے ہوئے ہیں) پر توجہ مرکوز کرے گا، اور متوازی دلائل طیارہ کو گھمانے کے بعد دوسرے پٹریوں پر لاگو ہوں گے۔ مماثل پوائنٹس اور اگر وہ ایک دوسرے کے قریب ترین پوائنٹس ہیں تو انہیں "مماثل" کہا جاتا ہے۔ واضح طور پر، پوائنٹس کی قریب ترین جوڑی ایک مماثل جوڑی ہے۔ پوائنٹس پر غور کریں اور، جیسے کہ بائیں طرف ہے اور اوپر بیان کردہ مرکز میں پچر میں واقع ہے۔ اگر قریب ترین نقطہ ہے، تو x سمت میں قریب ترین نقطہ (اس پچر میں) ہونا چاہیے۔ اس طرح، ایکس سمت میں قریب ترین پوائنٹس (اس پچر کے اندر) کے جوڑوں کا سیٹ قریب ترین پوائنٹس کے جوڑوں کے سیٹ کا ایک سپر سیٹ ہے۔ سیٹ P میں ہر پوائنٹ p = (x, y) کو ایک نئے پوائنٹ پر نقشہ بنائیں، جس سے تبدیل شدہ پوائنٹس کا سیٹ P 'بنتا ہے۔ نوٹ کریں کہ ایک پوائنٹ کے لیے، "مین" ویجز کے پوائنٹس اس نئے کوآرڈینیٹ سسٹم کے مقابلے میں بڑے یا چھوٹے ہوتے ہیں اور کوآرڈینیٹ ہوتے ہیں۔ پوائنٹس کو x، u اور v کوآرڈینیٹس سے ترتیب دیں، اور انہیں حرکی ترتیب شدہ فہرستوں میں محفوظ کریں۔ اندر کے مقامات پر 2D رینج ٹری T بنائیں۔ پرائمری ٹری میں ہر نوڈ ڈبلیو کے لیے، ٹی (ڈبلیو) کو ڈبلیو سے وابستہ ثانوی ٹری ہونے دیں۔ یہ رینج ٹری ایک پوائنٹ کے لیے "مین" ویج میں پوائنٹس کی شناخت کے لیے استعمال کیا جائے گا۔ پرائمری ٹری میں ہر نوڈ ڈبلیو کے لیے، اور ٹی (ڈبلیو) میں ہر نوڈ ای کے لیے، جوڑے (ڈبلیو، ای) = (بی، آر) کا حساب لگائیں، جہاں بی (یا آر) کو ای کے بائیں (یا دائیں) ذیلی ٹری میں زیادہ سے زیادہ (یا کم سے کم) ایکس-کوآرڈینیٹ کے ساتھ پوائنٹ کے طور پر بیان کیا گیا ہے۔ آئیے تمام جوڑوں ڈبلیو، ای کے لیے ٹی میں (ڈبلیو، ای) کا سیٹ بنیں۔ یہ قریب ترین پوائنٹس کے جوڑوں کے سیٹ کا ایک سپر سیٹ ہے (مرکزی پچر کے اندر)۔ جوڑوں پر ایک حرکی ترجیحی قطار بنائیں، جس میں ترجیحات کا تعین جوڑے میں موجود پوائنٹس کے درمیان فاصلے (اصل ہم آہنگی کے نظام میں ماپا جاتا ہے) سے ہوتا ہے۔ ہوائی جہاز کو گھمانے کے لیے مذکورہ بالا مراحل کو دہرائیں، تاکہ حرکی ترجیحی قطاریں بالترتیب چل سکیں۔ پی میں پوائنٹس کا قریب ترین جوڑا اوپر کی تین ترجیحی قطاروں سے حاصل کردہ کم از کم کم سے مطابقت رکھتا ہے۔ مینٹیننس سرٹیفکیٹ کی ناکامی ترجیحی قطاروں اور ترتیب دی گئی فہرستوں میں ہو سکتی ہے۔ پوائنٹس کی ترتیب میں تبادلہ T میں تبدیلیوں کا سبب بنے گا (جس میں وقت لگے گا)، اور ترجیحی قطاروں میں اندراج/حذف ہونے کا سبب بن سکتا ہے۔ نوٹ کریں کہ جیسا کہ اوپر بیان کیا گیا ہے سیٹوں میں تبدیلیوں کی تعداد مستقل نمبر ہونے کی ضرورت نہیں ہے۔ تاہم، کوئی بھی جوڑا جو پی اور کیو کی ترتیب کے نتیجے میں مماثل ہونا شروع یا رک جاتا ہے اس میں پی اور/یا کیو ہونا چاہیے، اور اس لیے مماثل جوڑوں کی صرف ایک مستقل تعداد ہوتی ہے جسے ترجیحی قطاروں میں داخل/حذف کیا جانا چاہیے۔ صرف ان مماثل جوڑوں کو اپ ڈیٹ کرنا ٹھیک ہے کیونکہ تعریف کے مطابق، صرف مماثل جوڑوں کے قریب ترین جوڑے ہونے کا امکان ہوتا ہے۔ تجزیہ یہ کے ڈی ایس ہے: ذمہ دار: کسی ایونٹ پر کارروائی کرنے میں وقت لگتا ہے مقامی: چونکہ ہر نقطہ حرکی ترتیب شدہ فہرستوں اور حرکی ترجیحی قطاروں کی مستقل تعداد میں موجود ہوتا ہے، اس لیے ان ڈھانچوں کے محل وقوع سے لوکیٹی کی پیروی کی جاتی ہے۔ کمپیکٹنیس: کمپیکٹنیس حرکی ترتیب شدہ فہرستوں اور حرکی ترجیحی قطاروں کی کمپیکٹنیس سے ہوتی ہے۔ موثر: ترتیب شدہ فہرستوں میں ہر تبادلہ حرکی ترجیحی قطاروں میں مستقل تعداد میں اندراج اور حذف ہونے کا سبب بنتا ہے۔ یہ فرض کرتے ہوئے کہ پوائنٹس کی حرکت فرضی الجبرائی ہے، تبادلوں کی ایک کثیر تعداد ہوتی ہے، اور اس لیے اس کے ڈی ایس کے ذریعے واقعات کی ایک کثیر تعداد پر کارروائی کی جاتی ہے، جس سے یہ موثر ہوتا ہے۔ یہ نقطہ نظر اعلی جہتوں میں قریب ترین جوڑے کو برقرار رکھنے کے لیے استعمال کیا جا سکتا ہے۔ حوالہ جات حرکی ڈیٹا ڈھانچے ہندسی ڈیٹا ڈھانچے