Consider the convex polytope in dimension $n$ with vertex set $V$ given by the origin and the $n$ points $$ e_i=\begin{bmatrix}0,\dots,0,\underset{i\text{-th coordinate}}{1},0,\dots,0\end{bmatrix}, i\in\{1,\dots,n\}. $$
Let $P$ be a point that lies inside the polytope. From every vertex $v\in V$, do the following:
- Get the direction of the line passing through $v$ and $P$.
- Extend such line from $P$ until the intersection with the boundary of the polytope.
The segments defined as above will split the polytope into $n+1$ sections. Here is a representation of this in 2D (where the sections are called $L_1$, $L_2$ and $L_3$).
Finally, consider another point $Q$ inside the polytope. I need an algorithm to determine which of the $n+1$ regions $Q$ belongs to.
For instance, in this scenario I would like the algorithm to output $L_3$.
The biggest challenge is that, in order for this algorithm to be useful, it should have a complexity of at most $O(n\cdot\log n)$ excluding any preliminary operations which does not need to be repeated as new input points come. In a nutshell, I am ok spending any number of operations to compute useful quantities, but then the test for a single point after these operations are performed should be $O(n\cdot \log n)$ at most.
