On Sat, Jan 28, 2012 at 08:12:52AM -0600, Andrei Alexandrescu wrote:
> On 1/27/12 11:02 PM, H. S. Teoh wrote:
> >If you treat the attributes as components of an n-dimensional vector, then you could recast the problem as the convex hull of k hypercuboids, where each hypercuboid lies between (0,0,0,...) and (x1,x2,x3,...). The points on the convex hull then are the high-ranking points (points inside the hull are obviously suboptimal). Furthermore, the closest points to the line spanned by the vector (1,1,1,...) are the points that maximize the most number of attributes.
> >
> >If you "peel away" the points on the convex hull, then the convex hull generated by the remaining points gives you the "second class" points. Peel away those, and the convex hull gives you the "third class" points, etc..
> >
> >Granted, this isn't exactly the original problem as stated, but it seems to be closer to what you intend to achieve with your stocks example.
> 
> That's close. Closer is to use simplexes instead of hypercubes. And the space is defined by rank, not the original features.
[...]

Actually, the reason I chose hypercubes was because I was hoping that the convex hull with hypercubes in the original features' space would be equivalent (or easily massaged to be equivalent) to using simplexes in rank space.  (Although the part about the (1,1,1,...) vector may not work out quite that nicely in this case.) Otherwise it doesn't really give you a good algorithm since you'll have to precompute the ranks.


T

-- 
War doesn't prove who's right, just who's left. -- BSD Games' Fortune

Andrei Alexandrescu wrote:

> we have multiple predicates, p1, p2, ..., pk. We want to sort elements in increasing order of rank(a, p1) + ... + rank(a, pk).

Got it. Thinking ocasionally.

-manfred

On 1/28/12 10:29 AM, H. S. Teoh wrote:
> Actually, the reason I chose hypercubes was because I was hoping that
> the convex hull with hypercubes in the original features' space would be
> equivalent (or easily massaged to be equivalent) to using simplexes in
> rank space.  (Although the part about the (1,1,1,...) vector may not
> work out quite that nicely in this case.) Otherwise it doesn't really
> give you a good algorithm since you'll have to precompute the ranks.

I understand. You're up to something; if you get to prove anything in that direction, I'd be interested. Thanks!

Andrei

Manfred Nowak wrote:

> Population and sweep would each be linear in time.

The sweep is linear in time only, if the populatable points of the area are bount by O(n), which is not neccessary the case.

Therefore, I don't see to find in the generell case a solution faster
than
   O( n + k*log( k)),
where `n' is the number of elements of the input and `k' is the
predefined number of "best of the breed" to be sorted.

-manfred