# Enumerating part of an arrangement

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?

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.
• 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 ? Jul 9, 2023 at 2:29