Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Let g_col(n) denote the relevant extremal quantity for colored radial orderings of bichromatic sets of 2n points. Quadratic colored-ordering conjecture. g_col(n)=Θ(n^2). The paper notes that bichromatic sets can have Θ(n^4) colored radial…
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. A hyperplane has nonzero regression depth in a subset when it…
Let P be a set of n points in the plane. Write w(P) for the length of a Euclidean minimum spanning tree of P, and let γ(P)=max_P=R∪ Bw(R)+w(B)/w(P), where the maximum is over all non-trivial bipartitions of P into two sets. Six-point…
Let K_3k+4 denote the complete graph on 3k+4 vertices, and let a semi-arc k-visibility graph be a graph represented by semi-arcs with visibility determined by at most k blockers. Complete-graph non-realizability conjecture. The complete…
Let S be a finite point set in cmathbbR^d. A simplicial half-net is a family of simplices determined by points of S such that every halfspace containing at least half the points of S contains one of these simplices. Simplicial half-net…
Let G be the polygonal domain under consideration, and let M(G) be its medial axis divided into K pieces. For N-1 discs, write the optimal way as n'_i_1^K, and for N discs write a way as n_i_1^K. The distance between pieces is counted by…
Let m be a positive integer, and let μ_1,…,μ_m be absolutely continuous measures in mathdsR^2. Kano's conjecture. There exists a curve in mathdsR^2 formed by horizontal and vertical segments, with at most m-1 turns, that bisects every…
For a point set in Euclidean space, the k-MAX-EMST-ratio problem restricts the input to k dimensions. Fixed-dimensional hardness conjecture. The k-MAX-EMST-ratio problem for k∈2,3 is NP-hard. The unrestricted MAX-EMST-ratio problem is…
Let d and 0≤ 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 regression depth at least ⌈ n/R(d,k)⌉. Conjectured formula for R(d,k).…
Let C be a compact convex figure in the plane, let α(C,k) denote the best worst-case aperture-angle approximation of C by an inscribed convex k-gon, and let α(k)=inf_Cα(C,k). A regular (k+1)-gon has interior angle (1-2/k+1)π. Fekete's…
An embedded shadow is a combinatorial model of a plane curve shadow, and \textnormal{\textsc{MinInflection}} denotes the decision problem asking whether the minimum inflection number is at most a prescribed bound. A building polygon has…
Let K be a p-dimensional simplicial complex in R^q, and let ε>0. Write M_ε for a subdivision of K, and M_ε' for a subcomplex of M_ε; let upvartheta_M_ε and upvartheta_M_ε' denote their simplicial regularity constants. The (p-1)-skeleton of…
Let n∈mathdsZ^+, and consider the point configuration called Polar Coordinates with parameter n. For a direction on the sphere, let the directed Discrepancy be the discrepancy measured in that direction. North Pole maximal directed…
Let d≥ 1, and consider finite point configurations of d+1 points in Euclidean space. Their Steiner ratio is the ratio of the cost of the optimal Steiner tree to the cost of the minimum spanning tree. Simplex-is-the-best conjecture. The d+1…
Let X be a set of N points, let K be the number of parts in an equal separation, and let d(Y) denote the minimum degree of a curve through a subset Y⊆ X. Equal-separation converse conjecture. If X cannot be separated equally, then max_Y⊆…
Let Y be an orientable 3-manifold with b_2(Y)=0, and let Knot Genus ask, given a knot K embedded in the 1-skeleton of a triangulation of Y and an integer g_0, whether g(K)3c= g_0. Knot Genus polynomial-time conjecture. The Knot Genus…
Let P be an integral orthogonal polygon, meaning that all its edges have integer length, and let N be its perimeter. The N/6 guard conjecture. The polygon P can always be guarded with at most ⌊ N/6 ⌋ guards. The best bound established in…
Let P⊆R^2 be a finite point set. A bipartite coloring is obtained by choosing a Euclidean minimum spanning tree of P and partitioning P=R∪ B so that every edge of the chosen tree has endpoints of different colors. Bipartite-coloring…
Let P be a generic set of n points in the plane. The linear lower-bound conjecture. cr-MST(P) ∈ Ω(n). The authors identify this as the most important problem for improving the lower bound for generic point sets. It would make the currently…
For a finite point configuration P⊂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 for P. Gilbert–Pollak Steiner ratio conjecture. The minimum Steiner ratio over…