Before revision:  We specialize Chazelle's dominance counting algorithm to points in the bounded integer plane and generalize it to trade reduced construction time for increased query time, since our partitioners make very few queries. Our algorithms split the original row (or column) ordering into parts to optimize diverse cost models. Combined with reordering or embedding techniques, our algorithms might be used to build more general heuristic partitioners, as they can optimally round one-dimensional embeddings of direct K-way noncontiguous partitioning problems .
After revision:  We specialize Chazelle's dominance counting algorithm to points in the bounded integer plane and generalize it to trade reduced construction time for increased query time, resulting in an overall linear runtime .