In 2D at least, there's a linear-time algorithm that works something like the linear-time median... According to the Cormen, Leiserson, Rivest & Stein _Algorithms_ book (the fat one with the mobile on the cover).

Oops, sorry, that's apparently when the input is a polygon. --Steve