205 problems

Grid-peeling convergence conjecture. As the grid is refined, the $m$-th convex layer of a convex curve converges to the ACSF after time $T$ when

A finite point set $S$ in Euclidean space admits standard Delaunay triangulations, and the mean radius functional and the $D$ functional are functionals defined on such triangulati…

Let $n$ be a positive integer, and let $\mu_1,\ldots,\mu_n$ be smooth measures in $\mathbb{R}^2$. An orthogonal path is a path formed only by horizontal and vertical segments, and…

Dedieu–Shub conjecture. The total curvature of the central path is linearly bounded in the dimension of the ambient space.

Bounded regularity subdivision conjecture. There exist $M_\epsilon$ and $M_\epsilon'$ such that

For positive integers $v\ge 3$ and $i\le v$, a point set is in almost convex position with parameters $(v,i)$ if it consists of the vertices of a convex $v$-gon together with $i$ i…

Let $A$ be a point set in general position in the plane, let $A_I$ be its set of interior points, and for each $W\subseteq A_I$ let $\mathcal{PT}_{W}(A)$ denote the pseudo-triangul…

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…

Polynomial source-image conjecture. There is a fixed polynomial $f_d$, independent of both $S$ and $v$, such that

Let $n$ denote the size parameter of the input plane graph, and consider the embedding algorithms developed in the paper for producing pseudo-triangulation embeddings. The near-lin…

Let $n\geq 2$, and consider the system of equations in $(v_1,\ldots,v_n,\lambda_1,\lambda_2)\in(\mathbb{C}^{*})^{n+2}$ given by the gradient and constraint equations in the paper.…

Let $T(d,k)$ be a constant such that, for every set of $n$ points with $k$ independent and $d-k$ dependent degrees of freedom, there is a $k$-flat $F$ and a partition of the points…

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 $n$ points be given in $\mathbb{R}^d$, and measure the quality of a regression hyperplane by its regression depth. Rousseeuw and Hubert's conjecture asserts that a regression h…

Let the dilation of a geometric graph be the maximum, over pairs of vertices, of the ratio between the shortest-path length in the graph and their Euclidean distance. Chew's conjec…

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…

Consider the volume problem of approximating the volume of a convex body using the oracle model studied in the source. Volume complexity conjecture. Although the best known algorit…

Let $P$ be a simple polygon with $n$ sides. A flipturn rotates a pocket of $P$ by $180$ degrees about the midpoint of its lid. Joss–Shannon's conjecture. Every simple polygon with…

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…

For a finite point set $V\subset\mathbb{R}^d$, a source $s\in V$, and $\epsilon>0$, a Steiner shallow-light tree is a tree spanning $V$ that may use Steiner points, with root stret…

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…