Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
A touching set of strings is a finite family of strings in the plane in which no pair crosses, and it is k-touching if every point of the plane belongs to at most k strings. Linear coloring conjecture. There is a constant c>0 such that…
Let G be the polygonal domain under consideration and let M(G) be its medial axis, including its junction points. An optimal filling solution is a filling by N discs maximizing the paper's filling measure. Eventual junction-occupation…
Let δ be an initial curve contained in a convex region R of area A. For t>0, write δ'=δ(t) for its affine curve-shortening flow whenever it is defined. For each fixed n, choose a set P of An^2 obstacle points independently and uniformly at…
Let P_a be the stellated tetrahedron with vertices p_0=(1,1,1), q_0=(-a,-a,-a), p_1=(1,-1,-1), q_1=(-a,a,a), p_2=(-1,1,-1), q_2=(a,-a,a), p_3=(-1,-1,1), q_3=(a,a,-a), where edges join all p_i,p_j and p_i,q_j for i≠ j, and a∈(0.5,0.57). A…
Let P be a convex polyhedron, meaning the convex hull of a finite set of points in R^3 in convex position. A polyhedron is Rupert if there exist R_1,R_2∈SO(3) and t∈R^2 such that P∘ R_1(P_C)+t⊂ P∘ R_2(P^∘), where P:R^3→R^2 drops the…
Let an SOD be a spherical occlusion diagram, and let a swirl be the configuration defined in the paper, classified as clockwise or counterclockwise according to its orientation. Two-clockwise-and-two-counterclockwise swirls conjecture.…
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 R and one point of B, and whose interior contains no point of R∪ B.…
Let P and Q be two disjoint nonempty closed sets in Euclidean space, and let a k-sector be the geometric object associated with P and Q that separates their distance-based regions. Uniqueness conjecture. The k-sector of any two disjoint…
Let S be a finite point set in general position in the plane. A spanning path of S is a plane straight-line path containing every point of S. Such a path is α-open when all angles relevant to its openness are at most α. 3π/2-open spanning…
Let T_1 and T_2 be non-crossing spanning trees on the same set of n points. A flip replaces one edge of a non-crossing spanning tree by another edge so that the result is again a non-crossing spanning tree. The 3/2n flip-distance…
Let a Spherical Occlusion Diagram (SOD) be a finite collection of geodesic arcs on the sphere satisfying the axioms in the paper, and call an SOD irreducible if no proper subset is an SOD. For a polyhedron P and a viewpoint v that sees no…
Let G be the polygonal domain under consideration and let M(G) be its medial axis, including its junction points. A filling solution that is a local maximum is a filling by N discs whose filling measure is locally maximal. Eventual…
Let G be the polygonal domain under consideration, and let M(G) be its medial axis divided into K pieces. A way W is a distribution of N discs over these pieces, written W=n_i_1^K, N=∑_i^K n_i, with n_i∈N and n_i∈0,1 when the i-th piece is…
Let d ≥ 3 and let P be a lattice d-polytope. Lattice-polytope diameter conjecture. Computing a lattice diameter of P is an NP-hard problem. This would extend the established NP-hardness result from bounded semi-algebraic sets, even when…
For a finite point set in the plane and a red-blue partition, the chromatic crossing number is the number of crossings between an edge of EMST(R) and an edge of EMST(B). The maximum chromatic crossing number is the largest such number over…
Let P and Q be point sets in general position, meaning that no three points are collinear, with the same cardinality and the same number of points on their convex hulls. A triangulation T_P of P and a triangulation T_Q of Q are compatible…
Let X=p_1,…,p_n⊂ Q^2 be a set of points in general position, and let t(X) be the number of triangulations of the convex hull of X using all points of X. Plane-triangulation conjecture. The function t is almost complete, meaning that it…
Let G be an inner triangulation of a 5-gon, and let F be an initial five color forest of G. The algorithm described above produces iterates for these data. Termination conjecture. The algorithm terminates with a non-negative solution for…
Let S be a finite point set in R^d, and let a triangulation of S be a subdivision of its convex hull into simplices whose vertices belong to S and whose interiors are pairwise disjoint. The superlinear triangulation conjecture. For each…
For each m, let S_m be a star with m children rooted at its centre vertex, chosen to maximise the length of the longest edge in the tree produced by the (δ,k)-PKRY algorithm, with every child at unit distance from the centre and no pair of…