It's likely that there is a better way. There already exist deterministic bitmap rasterizers which might yield decent results, and almost instantly. A greedy algorithm that tries to place the "most necessary" polygon first would almost certainly find a reasonable solution in a very short amount of time. Even a hybrid approach -- where the algorithm randomly picks a solution parameter and does a line search for the best value -- would converge faster than random hill-climbing alone.