We have an $x$-monotone path $\mathbb{P}$ in the input. We want to store the path $\mathbb{P}$ in a data structure such that we can answer this type of the query. Given any circle $\mathbb{C}$ and any two indices $i$ and $j$ with $1 \leq i \leq j \leq n$, report the first point of the subpath $\pi [ p_{i}, p_{j} ]=(p_{i},p_{i+1},...,p_{j}) $ is out of the $\mathbb{C}$.

We construct a balanced binary search tree storing the points $p_{1}, p_{2}, ... , p_{n}$ in its leaves. At each node of the tree, we store the extreme points of the convex hull of all points stored in its subtree.

To answer a query, we compute $\mathcal{O}(\log{}n)$ canonical nodes whose subtree span the vertices on the subpath $\pi [ p_{i}, p_{j} ]$. For each canonical node, we check whether or not the extreme points are in the $\mathbb{C}$. If all the extreme points lie inside $\mathbb{C}$, data structure reports $j$ otherwise it reports the first extreme point $L$ which is outside of the $\mathbb{C}$.

Now, I want to know what the worst Query time is.

  • $\begingroup$ Great. You have an algorithm. What have you tried so far? What prevents you from figuring out the running time? Where are you stuck? Go through each one of the steps of the algorithm see if you can figure out how much the running time of that step is. We're happy to help you learn the concepts, but we need to see what is preventing you from solving it on your own and where specifically you are stuck to have the best chance of helping you. $\endgroup$
    – D.W.
    May 30, 2018 at 16:37
  • $\begingroup$ In the worse case, all the point from i to j is located on the convex hull and we have to check j-i+1 points. So the worse query time is O(n). Is it true? $\endgroup$
    – Z.S.CS
    May 31, 2018 at 7:34
  • $\begingroup$ Don't guess. Work through the problem systematically. You described a process with multiple steps. I suggest you figure out what is the running time of each step. Then edit the question to show your work so far and which part you have a question about. It might help you to first write pseudocode for your approach, then analyze the running time of each line of the pseudocode. This will be a useful skill, and here's a wonderful chance to practice it! $\endgroup$
    – D.W.
    May 31, 2018 at 7:43


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.