Some embodiments of the invention provide a method for inserting several fills in an integrated circuit (“IC”) layout. The method identifies a set of potential fills in a region of an IC layout, where the set of potential fills has a first fill size, wherein the first fill size is from a set of fill sizes. The method specifies a halo around each potential fill in the set of potential fills. For each potential fill, the method determines whether the specified halo overlaps with a foreign object in the region of the layout. For each potential fill, the method specifies a legal fill in the region of the IC layout if the specified halo does not overlap with a foreign object in the region of the IC layout. The method inserts at least one legal fill in the region of the IC layout. In some embodiments, the halo is a spacing halo.