Zone theorem
ભૂમિતિમાં, ઝોન પ્રમેય એ એક પરિણામ છે જે રેખાઓની ગોઠવણીમાં રેખાના ઝોનની જટિલતાને સ્થાપિત કરે છે. વ્યાખ્યા એક રેખા વ્યવસ્થા, જે તરીકે સૂચવવામાં આવે છે, તે સમતલનું એક પેટાવિભાગ છે, જે રેખાઓના સમૂહ દ્વારા કોષો (-પરિમાણીય ચહેરાઓ), ધાર (-પરિમાણીય ચહેરાઓ) અને શિરોબિંદુઓ (-પરિમાણીય ચહેરાઓ) માં પ્રેરિત થાય છે. રેખાઓનો સમૂહ, રેખા વ્યવસ્થા અને એક રેખા (જેની સાથે સંકળાયેલી નથી) આપવામાં આવે તો, ઝોન એ દ્વારા છેદવામાં આવેલા ચહેરાનો સમૂહ છે. ઝોનની જટિલતા એ તેની સીમાની કિનારીઓની કુલ સંખ્યા છે, જેને એક કાર્ય તરીકે વ્યક્ત કરવામાં આવે છે. ઝોન થીયરમ જણાવે છે કે જટિલતા છે. ઇતિહાસ આ પરિણામ પ્રથમ વખત 1985 માં પ્રકાશિત થયું હતું; Chazelle et al. એક ગોઠવણીમાં રેખાના ઝોનની જટિલતા માટે ઉપરની સીમા આપી. 1991 માં, આ બાઉન્ડમાં સુધારો કરવામાં આવ્યો હતો, અને તે પણ દર્શાવવામાં આવ્યું હતું કે આ નાના એડિટિવ ફેક્ટર સુધીનું શ્રેષ્ઠ શક્ય અપર બાઉન્ડ છે. પછી, 2011 માં, રોમ પિંચાસીએ સાબિત કર્યું કે ગોઠવણીમાં રેખાના ઝોનની જટિલતા સૌથી વધુ છે, અને આ એક ચુસ્ત બાઉન્ડ છે. પ્રમેયના વિવિધ પુરાવાઓમાં ઉપયોગમાં લેવાતા કેટલાક દાખલાઓ ઇન્ડક્શન, સ્વીપ ટેકનીક, ટ્રી કન્સ્ટ્રક્શન અને ડેવનપોર્ટ-શ્ચિન્ઝેલ સિક્વન્સ છે. સામાન્યીકરણ જોકે સૌથી વધુ લોકપ્રિય સંસ્કરણ સમતલમાં રેખાઓની ગોઠવણી માટે છે, તેમ છતાં ઝોન પ્રમેયના કેટલાક સામાન્યીકરણ અસ્તિત્વમાં છે. દાખલા તરીકે, પરિમાણમાં, હાયપરપ્લેનની ગોઠવણીને ધ્યાનમાં લેતા, હાયપરપ્લેનના ઝોનની જટિલતા એ કોષોના સમૂહ (-પરિમાણીય ચહેરાઓ) દ્વારા છેદવામાં આવેલા પાસાઓ (-પરિમાણીય ચહેરાઓ) ની સંખ્યા છે. સમાનરૂપે,-પરિમાણીય ઝોન પ્રમેય જણાવે છે કે હાયપરપ્લેનના ઝોનની જટિલતા છે. પરિમાણ માટેના પ્રમેય માટે નોંધપાત્ર રીતે ઓછા પુરાવા છે. - પરિમાણીય કેસ માટે, સ્વીપ તકનીકો પર આધારિત પુરાવાઓ છે અને ઉચ્ચ પરિમાણો માટે યુલરના સંબંધનો ઉપયોગ થાય છેઃ અન્ય સામાન્યીકરણ રેખાઓ (અને હાયપરપ્લેન) ને બદલે સ્યુડોલીન (અને પરિમાણમાં સ્યુડોહાઇપરપ્લેન) ની ગોઠવણીને ધ્યાનમાં લે છે. પ્રમેય માટેના કેટલાક પુરાવા આ કિસ્સામાં સારી રીતે કામ કરે છે કારણ કે તેઓ તેમની દલીલો દ્વારા રેખાઓની સીધીતાનો નોંધપાત્ર રીતે ઉપયોગ કરતા નથી. પ્રેરણા વ્યવસ્થાઓમાં ઝોનની જટિલતાનો અભ્યાસ કરવાની પ્રાથમિક પ્રેરણા વ્યવસ્થાઓ બનાવવા માટે કાર્યક્ષમ અલ્ગોરિધમ્સની શોધમાંથી ઉદ્ભવે છે. શાસ્ત્રીય અલ્ગોરિધમ એ વૃદ્ધિશીલ રચના છે, જેને આશરે એક પછી એક રેખાઓ ઉમેરવા અને દરેક દ્વારા પેદા થયેલ તમામ બાજુઓને યોગ્ય ડેટા માળખામાં સંગ્રહિત કરવા તરીકે વર્ણવી શકાય છે (વ્યવસ્થા માટેનું સામાન્ય માળખું બમણું જોડાયેલ ધાર સૂચિ (ડીસીઇએલ) છે). અહીં, ઝોન થીયરમનું પરિણામ એ છે કે રેખાઓની કોઈપણ ગોઠવણીની સંપૂર્ણ રચના સમયસર કરી શકાય છે, કારણ કે દરેક રેખા દાખલ કરવામાં સમય લાગે છે. નોંધો સંદર્ભો. . . . . . . . . . પ્લેન ભૂમિતિમાં યુક્લિડિયન પ્લેન ભૂમિતિ પ્રમેયો