Vertex enumeration problem
গণিতে, একটি পলিটোপ, একটি পলিহেড্রাল কোষ কমপ্লেক্স, একটি হাইপারপ্লেন বিন্যাস, বা বিচ্ছিন্ন জ্যামিতির অন্য কোনও বস্তুর জন্য ভার্টেক্স গণনা সমস্যা হল বস্তুর কিছু আনুষ্ঠানিক উপস্থাপনা দেওয়া বস্তুর শীর্ষ নির্ধারণের সমস্যা। একটি ধ্রুপদী উদাহরণ হল রৈখিক বৈষম্যের একটি সেট দ্বারা নির্দিষ্ট একটি উত্তল পলিটোপের শীর্ষগুলির গণনার সমস্যাঃ যেখানে A হল একটি m × n ম্যাট্রিক্স, x হল চলকের একটি n × 1 কলাম ভেক্টর, এবং b হল ধ্রুবকের একটি m × 1 কলাম ভেক্টর। শীর্ষগুলি প্রদত্ত সীমানা বৈষম্যগুলি খুঁজে বের করার বিপরীত (দ্বৈত) সমস্যাটিকে ফ্যাসেট গণনা বলা হয় (কনভেক্স হুল অ্যালগরিদম দেখুন)। গণনামূলক জটিলতা সমস্যার গণনামূলক জটিলতা কম্পিউটার বিজ্ঞানের গবেষণার একটি বিষয়। সীমাহীন পলিহেড্রার ক্ষেত্রে, সমস্যাটি এনপি-হার্ড হিসাবে পরিচিত, আরও সুনির্দিষ্টভাবে বলতে গেলে, এমন কোনও অ্যালগরিদম নেই যা সম্মিলিত ইনপুট-আউটপুট আকারে বহুপদী সময়ে চলে, যদি না পি = এনপি হয়। ডেভিড অ্যাভিস এবং কোমেই ফুকুদার 1992 সালের একটি নিবন্ধে একটি বিপরীত-অনুসন্ধান অ্যালগরিদম উপস্থাপন করা হয়েছে যা ডি মাত্রায় (বা, দ্বৈতভাবে, ডি মাত্রায় এন পয়েন্টের উত্তল হুলের ভি দিকগুলি, যেখানে প্রতিটি দিক ঠিক ডি প্রদত্ত পয়েন্ট ধারণ করে) সময় O (ndv) এবং স্থান O (nd)-এ n বৈষম্যের একটি ননডিজেনারেট সিস্টেম দ্বারা সংজ্ঞায়িত একটি পলিটোপের v শীর্ষগুলি খুঁজে পায়। d মাত্রায় n হাইপারপ্লেনের একটি সহজ বিন্যাসে v শীর্ষগুলি O (n2dv) সময় এবং O (nd) স্থান জটিলতায় পাওয়া যায়। অ্যাভিস-ফুকুদা অ্যালগরিদম ওরিয়েন্টেড ম্যাট্রয়েডের জন্য ক্রিস-ক্রস অ্যালগরিদমকে অভিযোজিত করে। নোটস রেফারেন্স জ্যামিতিক অ্যালগরিদম রৈখিক প্রোগ্রামিং পলিহেড্রাল কম্বিনেটরিক্স পলিহেড্রা বিচ্ছিন্ন জ্যামিতি গাণিতিক সমস্যা গণনামূলক জ্যামিতি