Watchman route problem
વોચમેન પ્રોબ્લેમ એ કોમ્પ્યુટેશનલ ભૂમિતિમાં એક ઓપ્ટિમાઇઝેશન સમસ્યા છે જ્યાં ઉદ્દેશ એ છે કે માત્ર વિસ્તારનો નકશો આપવામાં આવેલા અવરોધો સાથે સમગ્ર વિસ્તારની સુરક્ષા માટે ચોકીદારે જે ટૂંકો માર્ગ લેવો જોઈએ તેની ગણતરી કરવી. પડકાર એ છે કે ચોકીદાર દરેક ખૂણાની પાછળ ડોકિયું કરે અને કયા ખૂણામાં મુલાકાત લેવી જોઈએ તે શ્રેષ્ઠ ક્રમ નક્કી કરે. આ સમસ્યાનું સમાધાન બહુપદી સમયમાં થઈ શકે છે જ્યારે સંરક્ષિત વિસ્તાર એક સરળ બહુકોણ હોય છે. છિદ્રોવાળા બહુકોણ માટે સમસ્યા એન. પી.-હાર્ડ છે, પરંતુ બહુપદી સમયમાં ઉકેલ દ્વારા અંદાજિત કરી શકાય છે, જેની લંબાઈ શ્રેષ્ઠના બહુપત્નીકીય પરિબળની અંદર હોય છે. આર્ટ ગેલેરીની સમસ્યા પણ જુઓ, જેમાં સમાન રીતે આપેલ વિસ્તારના તમામ બિંદુઓને જોવાનો સમાવેશ થાય છે, પરંતુ બહુવિધ સ્થિર ચોકીદારો સાથે.