IIRC, there's an even more powerful trick available: render the edges of a rectangle. If there are no color boundaries on the edges, you can usually assume it'll be solid-colored and skip rendering any of the contents. Some exceptions apply.
An enhancement to this method which I've seen is to check the edges of the rectangle for colour boundaries, and also check single random point inside. Presumably you can extend to n x n rectangles and k points inside as a function of n.
what are the exceptions? I thought that Mandelbrot was always guaranteed to be ok for this optimization (unlike, say, Julia)
The exception I'm aware of is when the rectangle is so large that it surrounds the entire set.
If you are doing colouring based on escape iterations this technique can elide detail.