CODEWITHSUNDEEP
c++algorithmgeometryplane
RazvanD
RazvanD

Reputation: 58

Maximize point in plane value

So, basically, I need a way to figure out what is the point in plane with the maximum value that has coordinates strictly less than a point.

One way to do it would be by checking all the points which has the complexity .

O(N) time, N being the number of points.
O(1) space.

Another way would be to do it with a binary indexed tree (BIT) which would give the complexity

O(log(max(X))*log(max(Y)) time, X being the maximum x coordinate and Y being the max y coordinate.
O(max(X)*max(Y)) space, this is the main problem, I can't afford that much space.

I would like something that has logarithmic complexity and as close as possible to O(N) space.

Example:

Example

Best values for each points are:

A -> 0 ( none )
B -> 2 ( A )
C -> 2 ( A )
D -> 0 ( none )
E -> 10 ( D )

Upvotes: 0

Views: 94

Answers (1)

David Eisenstat
David Eisenstat

Reputation: 65506

Here's an algorithm with O(N log N) construction time (O(N) if you're ambitious and implement one of the fancy data structures) and space and O(log N) time queries.

The idea is to take an incremental solution to the 1D problem with O(log N) time insertions and make the central data structure (a balanced binary search tree) partially persistent using standard techniques described on the linked Wikipedia page. To build the 2D data structure, sort the points by x increasing and then insert them in order into the 1D structure, saving references to the 1D snapshots in a list sorted by x. To query the 2D structure, binary search for the last snapshot before we inserted a point with point.x ≥ query.x, then do a 1D query.

To solve the 1D problem on the y-axis, we keep the non-dominated points in a balanced binary search tree. (A point is dominated if there is another point with lesser y and greater value.) To query, find the predecessor of query.y in the tree. To insert, first query y to make sure that the new point isn't dominated. If it's non-dominated, then insert it and delete points after it that it dominates. The amortized insertion time is O(log N).

Upvotes: 1

Related Questions