Bounds and Complexity for the Tessellation Problem