What is an algorithm to return free space in blocks of largest possible rectangles?
From your example it appears that you aren't asking to exclude overlap (e.g. 1 and 2 have the top-left segment in common), so perhaps this will suit your needs:
Divide the space into rectangles based on the corners identified by the occupied spaces.
Form the "basic rectangles" by extending line segments from those corners to the edges of the entire space.
Using any systematic order (e.g. top-to-bottom, left-to-right):
3.1. Select a basic rectangle and extend it as far as possible with other basic rectangles that have a side in common.
3.2. Form the set of all (unique) such extended rectangles.
Note that this searches/builds based on the "basic rectangles" from step 2, and not point-by-point throughout the entire space, so the performance should be much better.