کمپیوٹیشنل جیومیٹری

اصطلاح	term
شمارندگی ہندسہ	computational geometry

کمپیوٹیشنل جیومیٹری یا شمارندگی ہندسہ شاخ ہے شمارندی علم کی جو ایسے الخوارزم جن کا بیان ہندسہ کی اصطلاحات میں ہو سکے، کے مطالعہ کے لیے وقف ہے کچھ خالص ہندسی مسائل اُٹھتے ہیں شمارندگی ہندسہ الخوارزم کے مطالعہ میں اور ایسے مسائل کو شمارندگی ہندسہ کا حصہ سمجھا جاتا ہے۔

شمارندگی ہندسہ کی ترقی بطور علاحدہ شعبہ کا محرک کمپیوٹر تخطیط اور طرحبندہ ب کمپیوٹر اور تصنیع ( CAD /CAM) میں نشو و نما کی وجہ سے ہوئی، مگر شمارندگی ہندسہ میں بہت سے مسائل کلاسیکی فطرت کے ہیں اور ممکناً ریاضیاتی استصبار سے آتے ہیں۔

شمارندگی ہندسہ کے دوسرے اہم اطلاقیات میں شامل ہیں روبالیات (حرکت کی منصوبہ بندی اور استصباری مسائل)، جغرافیائی اطلاعات نظام (ہندساتی وقوع اور تلاش)، تکاملی دوران کی طرحبندی (IC کی طرحبندی اور جانچ پڑتال)، طرحبند ب ہندسہ (عددی تظبیط آلات کا پروگرامنگ کاری)۔

تولیفی شمارندگی ہندسہ

تولیفی شمارندگی ہندسہ میں تحقیق کا اولی مقصد ایسے مستعد الخوارام اور ڈیٹا ساختیں بنانا ہے جن سے اساسی ہندسہ اجرام: نقاط، لکیر قطعات، کثیر الاضلاع، کثیر الستوح، وغیرہ، کی اصطلاح میں بیان شدہ مسائل کو حل کیا جا سکے۔

ان میں سے کچھ مسائل اتنے سادہ معلوم ہوتے ہیں کہ کمپیوٹر کی آمد سے قبل انھیں مسائل ہی نہیں سمجھا جاتا تھا۔ مثال کے لیے دیکھو قریب ترین جوڑا مسئلہ:

مسطح میں n نقاط دیے ہوں، ایسے دو نقطے ڈھونڈو جن کا آپس میں فاصلہ کم ترین ہو۔

ہم نقاط کے تمام جوڑوں کے درمیان فاصلہ نکال سکتے ہیں، جن کی تعداد ہے اور پھر ان میں سب سے چھوٹے کا انتخاب کر سکتے ہیں۔ یہ منہ زور الخوارم O(n²) وقت لیوے ہے: یعنی اس کے اجری میں جو وقت درکار ہے وہ نقاط کی تعداد کے مربع کے متناسب ہے۔ شمارندگی ہندسہ میں ایک کلاسیکی نتیجہ ایسے الخورازم کی دریافت تھا جو O(n log n) وقت لیتا ہے۔

شمارندگی ہندسہ کا بھاری تمرکز شمارندگی مختلطی ہے چونکہ ان الخوارزموں کو بہت بڑے ڈیٹاطاقم پر استعمال کرنا مقصود ہوتا ہے جن میں لاکھوں کڑوروں نقاط ہو سکتے ہیں۔ بڑے ڈیٹا طاقموں کے لیے، O(n²) اور O(n log n) میں فرق ایسا ہے جیسے دنوں اور ثانیوں میں فرق۔

مسائل کی جماعتیں

شمارندگی ہندسہ میں مسائل درج ذیل جامع جماعتیں ممیز کی جاتی ہیں۔

ساکن مسائل

اس زمرہ میں ایسے مسائل آتے ہیں جس میں کچھ ادخال دیا گیا ہوتا ہے اور ارتباطی اخراج کی تعمیر کرنا ہوتی ہے۔ اس قسم کے کچھ بنیادی مسائل یہ ہیں: