In this paper we address the problem of segmenting a trajectory such that each segment is in some sense homogeneous. We formally define different spatio-temporal criteria under which a trajectory can be homogeneous, including location, heading, speed, velocity, curvature, sinuosity, andcurviness. We present a framework that allows us to segment any trajectory into a minimum number of segments under any of these criteria, or any combination of these criteria.In this framework, the segmentation problem can generally be solved in O(n log n) time, where n is the number of edges of the trajectory to be segmented.