Another crazy question. I'm wondering about the opposite to what you wrote about the proximity of the classification boundary: your input does not cover the full space - the points are probably denser in some regions than others and there are empty areas in this space. Based on my understanding of Voronoi partition, these empty areas will also be assigned to some clusters - practically at random. What if the problem is like in situation 1 from the attached picture?
The Voronoi partition would create the classification boundary assuming the populations really are separable. And, yes, it can be a bit random-seeming because the directions of the separating lines (or hyperplanes) that radiate off into empty space are defined entirely by only two data points which makes them extremely sensitive to the locations of those data points.
The more likely condition is an overlap in the populations such that a given region of the space has a non-zero probability of being associated with two or more types. That is, there may be some images of dogs that are indistinguishable from some images of cats.
If the training data points do not cover the full space, there's the fundamental problem that the empty parts really cannot be classified without making extrapolating assumptions about the distributions of the categories (i.e., how do the tails of the distributions extend into the empty space). Moreover, the empty space may correspond to objects not in the set of classified categories (e.g., velociraptors) or non-sense images (left-half cat, right-half dog images).