<p>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 <span class="math-container">$l_i \le A$</span> and <span class="math-container">$A_i \le u$</span> 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.</p>
<p>See the following for algorithms to do that: <a href="https://en.wikipedia.org/wiki/Vertex_enumeration_problem" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/Vertex_enumeration_problem</a>, <a href="https://cs.stackexchange.com/q/119562/755">https://cs.stackexchange.com/q/119562/755</a>, <a href="https://mathoverflow.net/q/203966/37212">https://mathoverflow.net/q/203966/37212</a>.</p>

CC BY-SA 4.0
2023-07-09T02:29:57.743Z
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 ?
Jarus
CC BY-SA 4.0
2023-07-09T01:59:59.373Z
2023-07-09T01:59:59.373Z
D.W.
<p>Consider an arrangement of hyper-planes in <span class="math-container">$d$</span> dimensional space. Let us say the attributes are <span class="math-container">$\{A_1, A_2, \cdots, A_d\}$</span>. If there was a constraint on say an attribute <span class="math-container">$A_i$</span> of the type <span class="math-container">$l_i \leq A_i \leq u_i$</span>, is there an efficient way to enumerate the vertices (0-simplex) in the arrangement which satisfy the constraint?</p>
<p>A naive way is to enumerate all vertices of the arrangement and check if they satisfy the constraint (<span class="math-container">$\mathcal{O}(n^d)$</span>). But I was wondering if <span class="math-container">$(1/r)$</span>-cuttings could be exploited in some manner to enumerate only those vertices that satisfy the constraint (<span class="math-container">$l_i \leq A_i \leq u_i$</span>) ?</p>
<p>Edit: Would enumerating only the intersection points that are formed from the intersection from the n hyperplanes - <span class="math-container">$\binom{n}{d}$</span> which lie within  (<span class="math-container">$l_i \leq A_i \leq u_i$</span>) be any easier?</p>

<computational-geometry><arrangements>
Enumerating part of an arrangement
Jarus
# Enumerating part of an arrangement

(Asked by: username_0 on 2023-07-08)

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?

**Tags:** computational-geometry, arrangements


---

## 1 answers

### Answer by username_1 on 2023-07-09. Score: 1 | Accepted answer

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>.

> **Comments:**
> **username_0**: 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 ?  

---

