  Regret minimizing sets are a very recent approach to representing a dataset D
with a small subset S of representative tuples. The set S is chosen such that
executing any top-1 query on S rather than D is minimally perceptible to any
user. To discover an optimal regret minimizing set of a predetermined
cardinality is conjectured to be a hard problem. In this paper, we generalize
the problem to that of finding an optimal k$regret minimizing set, wherein the
difference is computed over top-k queries, rather than top-1 queries.
  We adapt known geometric ideas of top-k depth contours and the reverse top-k
problem. We show that the depth contours themselves offer a means of comparing
the optimality of regret minimizing sets using L2 distance. We design an
O(cn^2) plane sweep algorithm for two dimensions to compute an optimal regret
minimizing set of cardinality c. For higher dimensions, we introduce a greedy
algorithm that progresses towards increasingly optimal solutions by exploiting
the transitivity of L2 distance.
