Questions tagged [arrangements]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0 votes
0 answers

Intersection of cuttings with a new hyperplane in d dimensions

Consider a d dimensional space with $n$ hyperplanes in general position. Based on these hyperplanes $n/r$ cuttings are constructed. If a new hyperplane is given, how many of the $d$-simplices from the ...
Jarus's user avatar
  • 38
1 vote
1 answer

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 ...
Jarus's user avatar
  • 38
2 votes
1 answer

Finding a cell in an arrangement of simplices

My question is n-dimensional, but I will begin by dropping the problem down to two dimensions for clarity's sake. It regards defining what is a solution by defining one or more data points that are ...
AaronF's user avatar
  • 123
10 votes
1 answer

Largest cell in an arrangement

Q. What is the complexity of finding the largest volume bounded cell in an arrangment of $n$ hyperplanes in dimension $d$? I feel I should know this... But I am not finding a definitive reference. ...
Joseph O'Rourke's user avatar
3 votes
1 answer

Emptiness of complement of subspace arrangement

Given $k$ affine subspaces in $\{0,1\}^n$, consider the problem of testing whether their union covers all of $\{0,1\}^n$. What's the complexity of this problem? P.S.: It seems that this can be ...
arnab's user avatar
  • 7,000