How to discern which color is "lower" and/or "higher" in CIE-L*a*b* colorspace for ordered dithering?

Question

I have implemented several functions to convert sRGB to the CIE-L*a*b* color space.

Now, I'd like to use that for dithering, but I'm unsure how to exactly discern which color is the "lower" color, and which one is the "higher" color.

When dithering in a one-dimensional color space (gray scale) things are easy. When using error diffusion dithering, I calculate the nearest gray scale value from my palette, and add the error to the surrounding pixels, depending on what kind of dithering matrix I use (for instance Floyd-Steinberg). Since this is one-dimensional, it's pretty easy, there is just this one value. But now I have this three dimensional color space, should I just add the error to each coordinate individually?
(This is the only way it makes sense to me, at this point.)

When dithering with an ordered dither matrix, things get even more complicated. Ordered dither matrices define a threshold value. For this, I need to know the "lower" pixel value, and the "higher" pixel value of my pallet, in regards to my current pixel that I'm about to dither. Now, I calculate the distance to both pixels, the threshold value from the dither matrix decides after which value between those to neighboring pixels, the pixel is either dithered to the lower, or to the higher pixel.
(The actual implementation would of course be more optimal than calculating that, by using a matrix that is sensibly chosen for the amount gray scale color values in my pallet. Also, things like choosing the pallet with evenly spaced color values, etc.)
This is - again - pretty easy in a one-dimensional color space. but in CIE-L*a*b*, there is no "higher" or "lower" value as such.

Using just the luminance to apply the threshold matrix to, seems pretty incorrect, I might have two colors with the same luminance in my pallet, then what?

Answer 1

This paper describes the problem very close to your question, and then proceeds to provide an algorithm to solve it:

http://ira.lib.polyu.edu.hk/bitstream/10397/1494/1/A%20multiscale%20color%20error_05.pdf

Hopefully this helps.