3

The problem at hand:

given a set of N points in an D dimensional space, with all their coordinates >= 0 (in 2D the points would all be in the 1st quadrant, in 3D in the 1st octant, and so on...), remove all the points that have another point that has value bigger or equal in every coordinate.

In 2D, the result is this: enter image description here

(image from Vincent Zoonekynd's answer here) and there is a simple algorithm, detailed in that answer, that runs in N*log(N). With chunking I should have brought it to N*log(H), but optimizations on that are for another question.

I was interested in extending the solution to 3 dimensions (and possibly 4, if it's still reasonable), but my current 3D algorithm is pretty slow, cumbersome and doesn't generalize to 4D nicely:

  • Sort points on the x axis, annotate the position of each point
  • Initialize a sort of segment tree with N leaves, where leaves will hold the points' y values and a node will hold max(child1, child2)
  • Sort points on the z axis
  • For every point from the largest z:
    • Check what position it was in the x order, try to put it in the segment tree in that position
    • Check first if there is a point already down (so it has > z), at an higher place (so it has > x) with a bigger y (this costs log(N), thanks tree)
    • If said point is found, the current point is discarded, otherwise it's inserted and the tree is updated

This still runs in N*log(N), but requires 2 different sorts and a 2*N-big structure.

Extending this would require another sort and a prohibitive 2*N^2-big quad tree.

Are there more efficient (especially CPU-wise) approaches?

I don't think it's relevant, but I'm writing in C, the code is here.

Community
  • 1
  • 1
12345ieee
  • 420
  • 1
  • 4
  • 15
  • I believe I have encountered your problem before - can you walk through an example of what you actually want to have happen, with a set of a few points for illustration? – D A Jun 02 '16 at 00:24
  • @DAdams I believe the image explains it much better than I can, just imagine it in 3D. You start with all the points there and the algorithm gives you back only the squares. In 2D it's easy to see. – 12345ieee Jun 02 '16 at 00:32
  • 1
    Worth noting that the same question was asked for c#, and the same solution I proposed was accepted http://stackoverflow.com/questions/12407730/finding-skyline-set – D A Jun 03 '16 at 19:16
  • @DAdams I missed that question, good find! I'm also a bit oblivious about SO's conventions on accepting/upvoting answers, but I'll accept and upvote yours only after I've understood _how_ I can use k-d trees to improve my algorithm. If instead I should upvote/accept more as "thank you for taking your time to answer", I will. – 12345ieee Jun 03 '16 at 19:45
  • So, the article linked in the other question: https://stackoverflow.com/questions/12407730/finding-skyline-set#comment16675154_12407730 basically answers my question in 2D and 3D (structures used apart, my algorithm is the same as the article authors). This question can be probably closed as duplicate. – 12345ieee Jun 03 '16 at 20:15

0 Answers0