Centroidal Voronoi tessellation
Inom geometri är en centroidal Voronoi tessellation ( CVT ) en speciell typ av Voronoi tessellation där genereringspunkten för varje Voronoi-cell också är dess tyngdpunkt (massacentrum). Det kan ses som en optimal partition som motsvarar en optimal fördelning av generatorer. Ett antal algoritmer kan användas för att generera centroidala Voronoi-tesselationer, inklusive Lloyds algoritm för K-means-klustring eller Quasi-Newton-metoder som BFGS .
Bevis
Gershos gissning, bevisad för en och två dimensioner, säger att "asymptotiskt sett är alla celler i den optimala CVT, samtidigt som de bildar en tessellation , kongruenta med en grundläggande cell som beror på dimensionen."
I två dimensioner är grundcellen för den optimala CVT en vanlig hexagon eftersom det har visat sig vara den tätaste packningen av cirklar i 2D-euklidiska rymden. Dess tredimensionella motsvarighet är den rombiska dodekaedriska honungskakan , härledd från den tätaste packningen av sfärer i 3D-euklidiska rymden.
Ansökningar
Centroidala Voronoi-tesselationer är användbara vid datakomprimering , optimal kvadratur , optimal kvantisering , klustring och optimal meshgenerering.
Ett viktat centroidal Voronoi-diagram är en CVT där varje centroid viktas enligt en viss funktion. Till exempel kan en gråskalebild användas som en densitetsfunktion för att vikta punkterna i en CVT, som ett sätt att skapa digital stippling .
Förekomst i naturen
Många mönster som ses i naturen är nära approximerade av en centroidal Voronoi-tesselation. Exempel på detta inkluderar Giant's Causeway , cellerna i hornhinnan och häckningsgroparna hos tilapiahanen .