大概“运行时间”在低时更好，而“解决方案质量”在高时更好。 为了使这些变量在表示属性的方式上更加一致，首先重新表示它们，以便高数字始终对应更好的值。对于这个问题，运行时的倒数（可以解释为每秒的运行次数）将是一个不错的选择，但运行时的负数也可以正常工作。

建立此约定后，我们可以通过将重新表达的“运行时”值与 x 坐标和“解决方案质量”值与 y 坐标相关联来绘制数据集中的每条记录，从而创建散点图。一条记录$(x,y)$ 支配另一个$(x',y')$当同时$x\ge x'$,$y\ge y'$， 和$(x,y) \ne (x',y')$. 没有理性的参与者（仅使用有关“运行时”和“解决方案质量”的信息）会选择被支配的选项$(x',y')$什么时候$(x,y)$——至少在两个属性上都一样好，至少在一个属性上更好——是可用的。因此，这样的参与者会将他们的兴趣集中在非支配选项上，并且可以自由地忽略所有其他选项。

由实心红色点主导的所有点都以灰色显示。它可以支配的所有可能点构成粉红色显示的（闭合）矩形。因为散点图中显然没有任何点支配实心点，所以它必须位于非支配边界上。

一组非支配选项形成散点图的“准凸包”或“非支配边界”的部分顶点。这是众所周知的凸包的模拟。实际上，准凸包在所有增加的变量单调重新表达下都是不变的，$f(x)$和$g(y)$，并且人们总能找到这样的重新表达，其中准凸包实际上变成了凸包。这种联系，以及凸包的优化构造的事实$n$积分要求$O(n\log(n))$计算，建议我们为准凸包寻找一种算法，该算法至少执行得一样好。存在这样的算法。这是R根据要求提供的一个，它被编写为可以轻松移植到其他计算平台：

hull.qc <- function(xy) {
  i <- order(xy[, 1], xy[, 2], decreasing=TRUE)
  frontier <- rep(0, length(i))
  k <- 0; y <- -Inf
  for (j in i) {
    if (xy[j, 2] > y) {
      frontier[k <- k+1] <- j
      y <- xy[j, 2]
    }
  }
  return(frontier[1:k])
}

它执行坐标的递减字典排序（时间：$O(n\log(n))$）然后扫描第一个坐标（时间：$O(n)$)，实施线扫描算法。记录发现第二坐标的新的较大值的点。返回它们在输入数组xy中的索引。

我们可以通过归纳证明这个算法是正确的。选择具有最大第一坐标和（在这些点中）最大第二坐标的初始点显然不受支配。使用它，我们可以消除它确实占主导地位的所有其他点，包括它自己。接下来在算法中遇到的第一个非消除点必然具有其第二坐标的较大值。它显然不受任何点的支配，因为如果是，则已经遇到了其他点。因此，该算法确实选择了非支配点，并且（通过对点数的归纳）它找到了所有点，QED。

为了说明这些概念和这个算法，这里是一个数据集的图$16$K 条记录（全部具有整数值，显示为抖动）及其准凸包（右上角的一条黑线），其顶点标记为问题中的要求，以及这些顶点的“优势矩形”着色。

进行计算、制作散点图并标记其准凸包顶点的代码如下所示。它包括一个稍快R的以hull.qc. 它在这台机器上大约在两秒钟内处理一百万个点。

#
# A faster solution (for R).
#
hull.qc <- function(xy) {
  i <- order(xy[, 1], xy[, 2], decreasing=TRUE)
  y <- xy[i, 2]
  frontier <- which(cummax(y) <= y)
  #
  # Eliminate interior points along edges of the hull.
  #
  y.0 <- y[frontier]
  frontier <- frontier[c(TRUE, y.0[-1] != y.0[-length(y.0)])]
  return(i[frontier])
}
#
# Generate data.
#
library(MASS)
set.seed(17)
n <- 2^14
xy <- floor(mvrnorm(n, c(1,1), matrix(c(1, -1/2, -1/2, 1), 2))^2)
#
# Do the work.
#
system.time(frontier <- hull.qc(xy))
xy.f <- xy[frontier, , drop=FALSE]
#
# Visualization.
#
plot(xy, xlab="X", ylab="Y", main="Quasiconvex Hull")
points(xy.f, pch=19, col="Red")