A collision-free formation reconfiguration trajectory subject to the linearized Hill’s dynamics of relative motion is analytically developed by extending an algorithm for gravity-free space. Based on the initial solution without collision avoidance constraints, the final solution to minimize the designated performance index and avoid collision is found, based on a gradient method. Simple simulations confirm that satellites reconfigure their positions along the safe trajectories, while trying to spend minimum energies. The algorithm is applicable to wide range of formation flying under the Hill’s dynamics.