Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Categories

Welcome to the new platform of Programmer's Heaven! We apologize for the inconvenience caused, if you visited us from a broken link of the previous version. The main reason to move to a new platform is to provide more effective and collaborative experience to you all. Please feel free to experience the new platform and use its exciting features. Contact us for any issue that you need to get clarified. We are more than happy to help you.

Finding the proper Algo (2D sorting)

I am supposed to create an O(n(logn)^2) algorithm wich, given as input a sequence S of points in the two dimensions (each point is discribed by a x value and a y value) the algorithm sould give or each point:

the number of elements from which each point is strictly bigger( both x and y bigger)

any help or idea would be appreciated!

Comments

  • XLoomXLoom Posts: 129Member
    I'd start with applying some standard sorting algorithm first to arrange points by x value. Sort these by using two memory buffers and splitting the original array bit by bit into those two arrays and merging them to original (can't remember the name of the algorithm, sorry) if x and y are simple floating point or double, that would give O(n*sizeof(x)*8). Then I think you can simply count the number of points Pj for each point Pi where Pj.y>Pi.y (j>i). I am not entirely sure if the complexity for this operation would be O(n(logn)^2), but it should be close and the result would be O(n*sizeof(x)*8) + O(n(logn)^2) which is roughly O(n(logn)^2) when we leave out the linear complexity of first operation. I may be wrong though, it's been a while since I have thought of any such algorithms and especially in terms of complexity.

    : I am supposed to create an O(n(logn)^2) algorithm wich, given as
    : input a sequence S of points in the two dimensions (each point is
    : discribed by a x value and a y value) the algorithm sould give or
    : each point:
    :
    : the number of elements from which each point is strictly bigger(
    : both x and y bigger)
    :
    : any help or idea would be appreciated!
    :
Sign In or Register to comment.