We present optimal algorithms for nadir (instrument pointing straight down) observation scheduling for spacecraft with fixed orbits. We present a comparison between an integer program formulation and a branch and bound formulation that makes use of a flow network heuristic, each capable of solving instances of these problems optimally. Neither technique strictly dominates the other, and we characterize their respective advantages and disadvantages. Note that this problem is NP-complete.