76 problems

Let $S$ be a set of $n$ points in $d$-dimensional space. The regression depth of a hyperplane is the minimum number of points intersected by the hyperplane as it undergoes a contin…

For a finite point configuration $P\subset\mathbb{R}^2$, let its Steiner ratio be the ratio of the cost of an optimal Steiner tree for $P$ to the cost of a minimum spanning tree fo…

Equivistal subdivision conjecture. The equivalence relation induced by equivistality constitutes a convex polyhedral subdivision of $S$. Moreover, the number of open regions in thi…

Polynomial combinatorial-type conjecture. The cardinality of the set of combinatorial types of shortest paths in $S$ is polynomial in the number of facets of $S$ when the dimension…

Let $d$ and $0\leq k<d$ be constants. For a set of points with $k$ independent and $d-k$ dependent degrees of freedom, let $R(d,k)$ denote a constant such that some $k$-flat has re…

Let $P$ be a set of $n$ points, and let regression depth be the minimum number of points intersected by a hyperplane during any continuous motion taking it to a vertical hyperplane…

Let $C$ be a compact convex figure in the plane, let $\alpha(C,k)$ denote the best worst-case aperture-angle approximation of $C$ by an inscribed convex $k$-gon, and let…

Let $\Omega$ be the shot-parameter space, let $c_0^{\varepsilon}$ denote the initial cue-ball configuration with ball radius or clearance parameter $\varepsilon$, and let…

Complexity conjecture. For an appropriate purely combinatorial encoding of embedded shadows, the decision problem $\textnormal{\textsc{MinInflection}}$ for unrestricted shadows is…

Let $\mathcal{P}_a$ be the stellated tetrahedron with vertices … … … … where edges join all $p_i,p_j$ and $p_i,q_j$ for $i\ne j$, and $a\in(0.5,0.57)$. A polyhedron is Rupert if it…

Let $\mathcal{P}$ be a polyhedron. It is Rupert if there exist $R_1,R_2\in\operatorname{SO}(3)$ and $t\in\mathbb{R}^2$ such that … where $P:\mathbb{R}^3\to\mathbb{R}^2$ drops the…

Let $\mathcal{P}$ be a convex polyhedron, meaning the convex hull of a finite set of points in $\mathbb{R}^3$ in convex position. A polyhedron is Rupert if there exist…

Let $\mathcal{T}$ be any locally finite triangulation of $\mathbb{R}^2$ and let $f$ be a continuous piecewise linear $\varepsilon$-approximation of $F(x,y)=xy$ with respect to…

Let $P$ be a finite point set in the plane, and let $\operatorname{cr-MST}(P)$ denote its bicolored minimum spanning tree crossing number. The NP-hardness conjecture. Finding…

Let $P$ be a generic set of $n$ points in the plane. The linear lower-bound conjecture. … The authors identify this as the most important problem for improving the lower bound for…

Let $d \geq 3$ and let $P$ be a lattice $d$-polytope. Lattice-polytope diameter conjecture. Computing a lattice diameter of $P$ is an $\operatorname{\mathsf{NP}}$-hard problem. Thi…

Let $Q_1,\ldots,Q_n$ be points and let $B_1,\ldots,B_n$ be edges of a convex hull, with each point matched to one edge and the resulting triangles considered as in the preceding he…

Let $P$ and $Q$ be two arbitrary point sets in general position with $|P|=|Q|$. Write $\operatorname{CH}(P)$ and $\operatorname{CH}(Q)$ for their convex hull vertex sets, and let a…

Let $X_{0}$ and $X_{1}$ be two sets of points in the Cartesian plane. Assume that no two line segments determined by four distinct points, with exactly two points from one set, int…

Linear slice conjecture. The restriction of $V$ to any straight line or flat plane in $\mathbb{R}^3$ has at most $O(n)$ equilibria.

Linear weighted-distance conjecture. The number of equilibria of the weighted Euclidean distance function defined by $n$ points with positive real weights in $\mathbb{R}^2$ is at m…

Bertsimas–Grigni conjecture. For every linear order $\leq$ on the unit square,

Directed-hyperarea vector identity. The directed-hyperarea vector satisfies

Let $S$ be a point set in general position. A plane spanning path on $S$ is a noncrossing straight-line spanning path, and the flip graph has these paths as vertices, with adjacenc…

Let $R$ and $B$ be disjoint sets of $n$ red and $n$ blue points, respectively, in the plane. An empty red-red-blue triangle is a triangle whose vertices consist of two points of…