1. A method comprising: receiving, at one or more processors, a sequence of coverage requirements for a region over a period of time, wherein the region is characterized by a plurality of landmarks and the period of time is divided into a plurality of time intervals, and wherein an individual coverage requirement of the sequence of coverage requirements identifies a desired number of vehicles of a plurality of vehicles for each of the plurality of landmarks at a given time interval; for one or more time intervals of the period of time, dividing, by the one or more processors, the region into a plurality of sub-regions such that for a first interval of the period of time, a given landmark of the plurality of landmarks is located in a first sub-region having a first size, and for a second interval of the period of time subsequent to the first interval, the given landmark is located in a second sub-region encompassing the first sub-region but having a second size that is larger than the first size; for the first interval of the period of time, determining by the one or more processors a set of one or more vehicles of the plurality of vehicles that are able to reach the given landmark in the first sub-region by an end of the first interval of the period of time; for the second interval of the period of time, determining by the one or more processors a set of one or more vehicles of the plurality of vehicles that are able to reach the given landmark in the second sub-region by an end of the second interval of the period of time, and based on the sequence of coverage requirements, generating, by the one or more processors, a fleet plan for the time intervals based on the determined set of one or more vehicles, wherein the generating occurs before any vehicle of the determined set of one or more vehicles travels to the given landmark, and wherein the fleet plan comprises instructions that cause at least one vehicle of the set of one or more vehicles to move in order to reach the given landmark; wherein determining by the one or more processors vehicles of the plurality of vehicles that can reach the given landmark in the first sub-region by the end of the first interval of the period of time comprises: determining starting locations of the set of one or more vehicles of the plurality of vehicles that are currently in operation and are configured to move in order to reach the given landmark; and based on the determined starting locations, determining vehicles of the plurality of vehicles that are currently in operation and can traverse a distance from the respective starting locations to the given landmark by the end of the first interval of the period of time, wherein the vehicles of the plurality of vehicles comprise balloons within a data network operable to provide data communication via optical or radio-frequency (RF) links, and wherein determining the vehicles of the plurality of vehicles that can traverse the distance from the respective starting locations to the given landmark by the end of the one or more time intervals comprises: receiving information indicative of an estimated wind direction and speed at given altitudes; estimating a distance and direction that the balloons would travel based on the estimated wind direction and speed at the given altitudes; and determining a sub-region of the plurality of sub-regions where the balloons would reside by traveling the estimated distance and direction.