Centroidal Voronoi tessellation
ભૂમિતિમાં, સેન્ટ્રોઈડલ વોરોનોઈ ટેસેલેશન (સીવીટી) એ એક ખાસ પ્રકારનું વોરોનોઈ ટેસેલેશન છે જેમાં દરેક વોરોનોઈ કોષનું ઉત્પાદન બિંદુ પણ તેનું સેન્ટ્રોઇડ (દળનું કેન્દ્ર) હોય છે. તેને જનરેટરના શ્રેષ્ઠ વિતરણને અનુરૂપ શ્રેષ્ઠ પાર્ટીશન તરીકે જોઈ શકાય છે. સંખ્યાબંધ અલ્ગોરિધમ્સનો ઉપયોગ સેન્ટ્રોઇડલ વોરોનોઈ ટેસેલેશન પેદા કરવા માટે થઈ શકે છે, જેમાં કે-મીન્સ ક્લસ્ટરિંગ માટે લોઈડના અલ્ગોરિધમનો અથવા બી. એફ. જી. એસ. જેવી અર્ધ-ન્યુટન પદ્ધતિઓનો સમાવેશ થાય છે. પ્રૂફ ગેર્શોનું અનુમાન, જે એક અને બે પરિમાણો માટે સાબિત થયું છે, તે કહે છે કે "લક્ષણવિહીન રીતે કહીએ તો, શ્રેષ્ઠ સી. વી. ટી. ના તમામ કોષો, ટેસેલેશન બનાવતી વખતે, મૂળભૂત કોષ સાથે એકરૂપ હોય છે જે પરિમાણ પર આધાર રાખે છે". બે પરિમાણોમાં, શ્રેષ્ઠ CVT માટેનો મૂળભૂત કોષ નિયમિત ષટ્કોણ છે કારણ કે તે 2D યુક્લિડિયન અવકાશમાં વર્તુળોનું સૌથી ગાઢ આવરણ સાબિત થાય છે. તેની ત્રિ-પરિમાણીય સમકક્ષ રોમ્બિક ડોડેકાહેડ્રલ હનીકોમ્બ છે, જે 3D યુક્લિડિયન અવકાશમાં ગોળાઓના સૌથી ગાઢ પેકિંગમાંથી મેળવવામાં આવે છે. એપ્લિકેશન્સ સેન્ટ્રોઈડલ વોરોનોઈ ટેસેલેશન ડેટા કમ્પ્રેશન, શ્રેષ્ઠ ચતુર્થાંશ, શ્રેષ્ઠ ક્વોન્ટાઇઝેશન, ક્લસ્ટરિંગ અને શ્રેષ્ઠ મેશ જનરેશનમાં ઉપયોગી છે. ભારિત સેન્ટ્રોઈડલ વોરોનોઈ આકૃતિ એ સીવીટી છે જેમાં દરેક સેન્ટ્રોઈડને ચોક્કસ કાર્ય અનુસાર ભારિત કરવામાં આવે છે. ઉદાહરણ તરીકે, ગ્રેસ્કેલ ઇમેજનો ઉપયોગ ડિજિટલ સ્ટીપલિંગ બનાવવાની રીત તરીકે સીવીટીના બિંદુઓને વજન આપવા માટે ઘનતા કાર્ય તરીકે થઈ શકે છે. પ્રકૃતિમાં બનતું સ્વરૂપ પ્રકૃતિમાં જોવા મળતી ઘણી પેટર્નને કેન્દ્રસ્થ વોરોનોઈ ટેસેલેશન દ્વારા નજીકથી અંદાજવામાં આવે છે. આના ઉદાહરણોમાં જાયન્ટ્સ કોઝવે, કોર્નિયાના કોષો અને નર તિલાપિયાના સંવર્ધન ખાડાઓનો સમાવેશ થાય છે. સંદર્ભો અલગ ભૂમિતિ ભૌમિતિક અલ્ગોરિધમ્સ આકૃતિઓ