Is there a way to compute vertex density?
Assuming Cycles, the simplest method is to use the Point Density node.



The Point Density texture calculates the distances from a set of points and can be set to either take those points from a Particle system or from mesh vertices. By using Object Vertices and setting the Object to itself, it will provide the density of the vertices of its own mesh. In the above example, the Vector Transform node is used to translate Object coordinates into World coordinates to drive the Point Density. This ensures that the Point Density is in the same location as the mesh.

Adjust the Radius to affect the influence of each vertex (higher values increase the distance at which each vertex will have an effect - effectively smoothing it out further), increase the Resolution if the results are 'blocky' (higher values will be slower to compute) and adjust the Multiply node to scale the result (here I divide by 1000 to bring it within the range 0.0 to 1.0 for the Emission node).

EDIT : Here's an example using the example from the original question. I've adjusted the settings to produce reasonable results without the circular artifacts mentioned by @LukeD. The artifacts are due to the Point Density also providing values between the vertices (rather than LukeD's approach that generates distinct vertex colors). The artifacts can be minimised by adjusting the Point Density properties - Radius, Interpolation, Resolution as shown :