Vertex enumeration problem
ગણિતમાં, પોલીટોપ, પોલીહેડ્રલ કોષ સંકુલ, હાયપરપ્લેન ગોઠવણી અથવા અન્ય કોઈ અલગ ભૂમિતિ માટે શિરોબિંદુ ગણતરી સમસ્યા એ પદાર્થની કેટલીક ઔપચારિક રજૂઆતને ધ્યાનમાં રાખીને પદાર્થના શિરોબિંદુઓના નિર્ધારણની સમસ્યા છે. એક શાસ્ત્રીય ઉદાહરણ એ રેખીય અસમાનતાઓના સમૂહ દ્વારા નિર્દિષ્ટ બહિર્મુખ બહુપદીના શિરોબિંદુઓની ગણતરીની સમસ્યા છેઃ જ્યાં A એ m × n મેટ્રિક્સ છે, x એ ચલોનો n × 1 સ્તંભ વેક્ટર છે, અને b એ સ્થિરાંકોનો m × 1 સ્તંભ વેક્ટર છે. શિરોબિંદુઓને આપવામાં આવેલી બાઉન્ડિંગ અસમાનતાઓ શોધવાની વ્યસ્ત (દ્વિ) સમસ્યાને ફેસેટ એન્યુમરેશન કહેવામાં આવે છે (કન્વેક્સ હલ એલ્ગોરિધમ્સ જુઓ). કોમ્પ્યુટેશનલ જટિલતા સમસ્યાની કોમ્પ્યુટેશનલ જટિલતા એ કોમ્પ્યુટર વિજ્ઞાનમાં સંશોધનનો વિષય છે. અનબાઉન્ડ પોલિહેડ્રા માટે, સમસ્યા એન. પી.-હાર્ડ તરીકે ઓળખાય છે, વધુ ચોક્કસપણે, ત્યાં કોઈ અલ્ગોરિધમ નથી કે જે સંયુક્ત ઇનપુટ-આઉટપુટ કદમાં બહુપદી સમયમાં ચાલે, સિવાય કે પી = એન. પી. ડેવિડ એવિસ અને કોમેઈ ફુકુડાના 1992ના એક લેખમાં રિવર્સ-સર્ચ અલ્ગોરિધમ રજૂ કરવામાં આવ્યું છે, જે સમય O (ndv) અને જગ્યા O (nd) માં d પરિમાણોમાં (અથવા, દ્વિસંગી રીતે, d પરિમાણોમાં n બિંદુઓના બહિર્મુખ પતવારના v પાસાઓ, જ્યાં દરેક પાસામાં બરાબર d આપેલ બિંદુઓ હોય છે) n અસમાનતાની બિન-આનુવંશિક પ્રણાલી દ્વારા વ્યાખ્યાયિત પોલીટોપનાં v શિરોબિંદુઓને શોધે છે. d પરિમાણોમાં n હાયપરપ્લેનની સરળ ગોઠવણીમાં v શિરોબિંદુઓ O (n2dv) સમય અને O (nd) અવકાશ જટિલતામાં મળી શકે છે. એવિસ-ફુકુડા અલ્ગોરિધમે ઓરિએન્ટેડ મેટ્રોઇડ્સ માટે ક્રિસ-ક્રોસ અલ્ગોરિધમનો સ્વીકાર કર્યો હતો. નોંધો સંદર્ભો ભૌમિતિક અલ્ગોરિધમ્સ રેખીય પ્રોગ્રામિંગ પોલિહેડ્રલ સંયોજન પોલિહેડ્રા અલગ ભૂમિતિ સંખ્યાત્મક સંયોજન ગાણિતિક સમસ્યાઓ કોમ્પ્યુટેશનલ ભૂમિતિ