3
$\begingroup$

Assume we have a convex polytope that is formed by the intersection of $k$-halfspaces in $\mathbb{R}^{n}$.

$$ a_{0,0}x^{n-1} + {a}_{0,1}x^{n-2} + ... a_{0,n-1} \leq 0 $$ $$ a_{1,0}x^{n-1} + {a}_{1,1}x^{n-2} + ... a_{1,n-1} \leq 0 $$ $$ a_{2,0}x^{n-1} + {a}_{2,1}x^{n-2} + ... a_{2,n-1} \geq 0 $$ $$ .... $$ $$ a_{k-1,0}x^{n-1} + {a}_{k-1,1}x^{n-2} + ... a_{k-1,n-1} \leq 0 $$

How do I quickly and efficiently test that some point $x \in \mathbb{R}^n$ lies inside this polytope ?

I would ideally like this computation to be done as efficiently as possible ?

(What I know so far ? If there were $k$ points in $\mathbb{R}^n$ forming the convex hull and we have to test if $x$ lies inside this hull, then we can frame this as a linear programming problem. I was wondering if the same treatment applies when they are halfspaces also ?)

Improve this question
$\endgroup$
6
  • 2
    $\begingroup$ You have already written your problem as a linear program. The Simplex Method does not care whether your polyhedron is bounded or not. $\endgroup$
    – Tony Huynh
    Sep 23, 2015 at 15:54
  • 1
    $\begingroup$ If you construct a Dobkin-Kirpatrick hierarchical data structure for the polytope of $m$ vertices, then point location can be accomplished in $O(\log m)$ time per query. $\endgroup$
    – Joseph O'Rourke
    Sep 23, 2015 at 16:13
  • $\begingroup$ Why not simply plug the value of $x$ in those $k$ inequalities ? $\endgroup$
    – F_G
    Sep 24, 2015 at 7:40
  • $\begingroup$ @F_G : That will involve a matrix multiplication which will be time-consuming for hidim data. I was hoping for a smaller time inequality check. Sorry if I have misunderstood the problem. $\endgroup$
    – rajaditya_m
    Sep 28, 2015 at 0:40
  • $\begingroup$ @JosephO'Rourke : That looks interesting. I will refernece it $\endgroup$
    – rajaditya_m
    Sep 28, 2015 at 0:40

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.