You can optimize Brute force search:
For each point in plane compute how big disk (for example, can be arbitrary bounds) can be placed without colision.
set of (x, y, area of biggest shape to fit at the position)
Sort this by third parameter ("area of biggest shape to fit at the position").
sorted set of (x, y, area of biggest shape to fit at the position) by third value
Compute bounds of Your shape (one You want to place into grid) which are consistent with the sorted set. If You are lucky Your shape would be small enought to be enclosed by one in the sorted set. Finding which one it is is O(log N) for binary search.
Also note, that if You know what sort of shapes are going to be there You can precompute more.