In various embodiments, a subsequence-based encoding application generates a convex hull of subsequence encode points based on multiple encoding points and a first subsequence included in a set of subsequences that are associated with a media title. The subsequence-based encoding application then generates a first encode list that includes multiple subsequence encode points based on the first convex hull. Notably, each subsequence encode point included in the first encode list is associated with a different subsequence. The subsequence-based encoding application selects a first subsequence encode point included in the first encode list based on a first variability constraint that is associated with a media metric. The subsequence-based encoding application then replaces the first subsequence encode point included in the first encode list with a second subsequence encode point to generate a second encode list. Finally, the subsequence-based encoding application generates an encoded media sequence based on the second encode list.