Before revision:  Furthermore, we show that in two dimensions one can solve this problem using O( \mathrm{price (P,C) \log^2 n ) oracle queries, where \mathrm{price (P, C) is the minimal number of queries that any algorithm for this specific instance requires.
After revision:  Furthermore, we show that in two dimensions one can solve this problem using O( v (P,C) \log^2 n ) oracle queries, where \mathrm{price (P, C) is the minimal number of queries that any algorithm for this specific instance requires.