1

I was wondering if R enables to print (or highlight) only the points of the input data set that are Pareto-optimal.

For example, in the below 2D plot you can observe a set of 50 points. I would like to be able to print the Pareto-optimal points with different colours. In this example, consider that the two two dimensions are to be minimised.

http://i42.tinypic.com/jso7ma.png

Any tips?

Edit:

According to a comment, I achieved the desired result with the following code:

n <- 40
d <- data.frame(
  x = rnorm(n),
  y = rnorm(n)
)
# We want the "extreme" points in the following plot
par(mar=c(1,1,1,1))
plot(d, axes=FALSE, xlab="", ylab="")
for(i in 1:n) {
  polygon( c(-10,d$x[i],d$x[i],-10), c(-10,-10,d$y[i],d$y[i]), 
  col=rgb(.9,.9,.9,.2))
}


d <- d[ order(d$x, decreasing=FALSE), ]
result <- d[1,]
for(i in seq_len(nrow(d))[-1] ) {
  if( d$y[i] < result$y[nrow(result)] ) {
    result <- rbind(result, d[i,])  # inefficient
  } 
}
points(result, cex=2, pch=15)
Dio
  • 684
  • 2
  • 9
  • 18
  • Related question: http://stackoverflow.com/questions/9106401/implementation-of-skyline-query-or-efficient-frontier – Vincent Zoonekynd Jun 17 '13 at 15:49
  • Thanks a lot. Any ideas to do it in 3D? The above method is convenient for 2D as you keep the one dimension fixed. – Dio Jun 17 '13 at 16:32
  • In that question, the `sqldf`-based solution should be easy to adapt. If your dataset is small, the performance (cubic...) should not be a problem. – Vincent Zoonekynd Jun 17 '13 at 17:21
  • In that question, I posted a link and some explanation to my [rPref](http://www.p-roocks.de/rpref) package which solves this problem. – Patrick Roocks Aug 05 '14 at 09:56

1 Answers1

1

Here's a solution using chull (convex hull of a set of points). Warning: untested.

# assume d is your matrix or data frame of points
ch <- d[chull(d), ]
ch[apply(ch, 1, function(p) !any(ch[, 1] < p[1] & ch[, 2] < p[2])), ]

You could extend this to >2 dimensions by replacing chull with your own convex hull algorithm, say one of those from here, and extending the conditional test to fit.

Hong Ooi
  • 56,353
  • 13
  • 134
  • 187