1
$\begingroup$

Consider an arrangement of hyper-planes in $d$ dimensional space. Let us say the attributes are $\{A_1, A_2, \cdots, A_d\}$. If there was a constraint on say an attribute $A_i$ of the type $l_i \leq A_i \leq u_i$, is there an efficient way to enumerate the vertices (0-simplex) in the arrangement which satisfy the constraint?

A naive way is to enumerate all vertices of the arrangement and check if they satisfy the constraint ($\mathcal{O}(n^d)$). But I was wondering if $(1/r)$-cuttings could be exploited in some manner to enumerate only those vertices that satisfy the constraint ($l_i \leq A_i \leq u_i$) ?

Edit: Would enumerating only the intersection points that are formed from the intersection from the n hyperplanes - $\binom{n}{d}$ which lie within ($l_i \leq A_i \leq u_i$) be any easier?

$\endgroup$

1 Answer 1

1
$\begingroup$

This is equivalent to asking for how to enumerate all vertices of a simplex, given the inequalities that define it (since you can just add $l_i \le A$ and $A_i \le u$ as two additional inequalities that define the simplex). There can be exponentially many such vertices, so any algorithm can take exponential time in the worst case.

See the following for algorithms to do that: https://en.wikipedia.org/wiki/Vertex_enumeration_problem, https://cs.stackexchange.com/q/119562/755, https://mathoverflow.net/q/203966/37212.

$\endgroup$
1
  • $\begingroup$ Would the problem of enumerating only the point intersection of the hyper-planes instead of all the vertices be any simpler ? there are $\binom{n}{d}$ intersections that give rise to intersection points. would enumerating only a part of them that satisfy the linear inequality be any easier ? $\endgroup$
    – Jarus
    Jul 9, 2023 at 2:29

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.