I'm not sure but perhaps the classic *Géométrographie* by [Lemoine][1] discusses this space complexity as well as time complexity. See also http://www.cs.mcgill.ca/~sqrt/cons/constructions.html and http://geometrographie.org/ .

I think I once saw a paper about space complexity but I can't find it right now.


  [1]: http://en.wikipedia.org/wiki/Emile_Lemoine