Abstract A novel algorithm for monitoring marine environments utilizing a resource-constrained robot is presented in this paper. Collecting water quality data from large bodies of water is of paramount importance for monitoring the health of the ecosystem, particularly for predicting harmful cyanobacteria blooms. The large spatial dimensions of such bodies of water, together with the slow varying of parameters in water bodies makes exhaustive complete coverage impractical and unnecessary. In this work, we explore a new strategy for efficient measurement of water quality quantities with an autonomous surface vehicle (ASV). The method utilizes the medial axis of the body of water and prunes redundant branches, producing a guideline ASV trajectory that visits representative areas of the environment. The proposed method ensures that data are collected in the narrower parts of the lake, where harmful blooms have historically been observed, while also visiting open water areas. An analysis of the spatio-temporal sensitivity of the target sensor is presented. A comparison with the traditional lawnmower algorithm demonstrates superior performance in terms of area covered within the available execution length. Offline analysis for several lakes and reservoirs together with results from field deployments at Lake Murray, SC, USA demonstrate the effectiveness of the proposed method.