How to divide earth into polygons based on a collection of labeled coordinates?

I have around one million labeled coordinates(latitude, longitude) all around the world, with around 10,000 unique labels(location_id).

Each point corresponds to exactly one class(location_id). Each class is densely distributed over 1-10km. radius; With more density around its centroid.

How can I create an earth multi-polygon consisting of 10,000 polygons? Basically dividing the earth into 10,000 polygons. The separation would be based on the density of points in each location. The more points clumped in a location, the bigger its polygon's radius.