Priority queue where values are a sum of two currencies and popMin takes an exchange rate

Question

I want to define a priority queue where priorities have components in two different currencies. For example, Item A costs 1 USD + 20 yen. This queue has two methods, insert(priceInUsd, priceInYen) and popMin(exchangeRate), which takes a price of a US dollar in yen, and pops the item with the lowest total cost in USD and yen given this exchange rate. How do I implement this?

Here are my ideas so far:

• Use a k-d tree. Insertion takes log(n). I think you can implement findMin by a minor modification to the normal k-d tree nearest-neighbor algorithm, so this should allegedly take log(n) time. Wikipedia is kind of hedgey about whether k-d tree nearest-neighbour is really log(n) worst case if you have terrible data, so I'm not sure about this. Also, I've never seen a particularly reliable-looking source claim that kd-trees allow log(n) insertion.
• Maintain the convex hull of the points, and loop over everything in it when you want to getMin. Worst case n, but if there are only normally n**(1/3) things in your convex hull, this is alright on average.

Answer 1

There's some prior art that you didn't mention, on the dynamic planar convex hull problem. Brodal and Jacob (FOCS '02) give a data structure that lets you insert a point, delete a point, and find the extreme point in a direction in amortized logarithmic time, which suffices to implement your data structure (though the implementation looks complicated).