In this paper we address the problem of segmenting a trajectory based on spatiotemporalcriteria. We require that each segment is homogeneous in the sense that a setof spatiotemporal criteria are fulfilled. We define different such criteria, including location,heading, speed, velocity, curvature, sinuosity, curviness, and shape. We present an algorithmicframework that allows us to segment any trajectory into a minimum number ofsegments under any of these criteria, or any combination of these criteria. In this framework,a segmentation can generally be computed in O(n log n) time, where n is the numberof edges of the trajectory to be segmented. We also discuss the robustness of our approach.