Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
A 1-intersecting set of strings is a set of strings in which any two strings intersect in at most one point, and it is k-touching if every point of the plane belongs to at most k strings. Additive coloring conjecture. There is a constant…
Let A ⊆ R^2 be finite and generic. For every 1 ≤ k ≤ |A|-1, let F_k be the family of level-k hypertriangulations that have the local angle property, and let P_k ∈ F_k. Order-k Delaunay optimality conjecture. The hypertriangulation P_k has…
Let G be any graph. A rectilinear drawing represents the vertices of G by points in the plane and its edges by straight-line segments. A convex-polygon drawing is one in which all vertices are vertex points of a convex polygon.…
Let T be any locally finite triangulation of R^2 and let f be a continuous piecewise linear ε-approximation of F(x,y)=xy with respect to T. Optimality conjecture. The triangle density satisfies δ(T) ≥ frac√38ε. The bound is proved for…
An ordered curve pseudo-visibility graph is the ordered graph arising from the pseudo-visibility representation by curves discussed in the paper. Recognition conjecture. Ordered curve pseudo-visibility graphs can be recognized in…
Let d be the degree and let n be the number of variables. For a generic hypersurface in R^n, its Voronoi degree is the degree of the corresponding Voronoi ideal. For a generic homogeneous polynomial, its zero set is a cone. Voronoi degree…
Let P be a finite point set in the plane, and let cr-MST(P) denote its bicolored minimum spanning tree crossing number. The NP-hardness conjecture. Finding cr-MST(P) is NP-hard. This concerns the computational complexity of the bicolored…
Let A_1,…,A_n∈R^2 be points with positive real weights, and consider the associated weighted Euclidean distance function. Its equilibria are the critical points of this function. Linear weighted-distance conjecture. The number of…
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 adjacency defined by a flip. Akl et al.'s conjecture. The flip graph of…
Let Q_1,…,Q_n be points and let B_1,…,B_n be edges of a convex hull, with each point matched to one edge and the resulting triangles considered as in the preceding heuristic. Termination conjecture. The algorithm described above always…
Let S be a set of n points in the plane, and let a polygonization of S be a simple polygon whose vertex set is S. Natural conjecture. There exists a polygonization of S with every interior angle of measure at most 2π-2π/n-1. The bound…
Let Ω be the shot-parameter space, let c_0^ε denote the initial cue-ball configuration with ball radius or clearance parameter ε, and let N(c_0^ε,x) be the number of balls pocketed from initial state c_0^ε under shot parameters x.…
Let P be a polyhedron. It is Rupert if there exist R_1,R_2∈SO(3) and t∈R^2 such that P∘ R_1(P)+t⊂ P∘ R_2(P^∘), where P:R^3→R^2 drops the x-coordinate and P^∘ is the interior of P. Steininger–Yurkevich conjecture. The rhombicosidodecahedron…
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, intersect unless the endpoints of one segment belong to different…
Let T be a finite, orientable triangulation with o vertices and m edges admitting a hyperbolic structure. A hyperbolic structure is generic when the stated property holds except on a closed measure-zero set of hyperbolic structures on T.…
Let a matrix weighted rational Bézier curve be defined by Equation, with weight matrices given by Equation or Equation. Let the real weights be computed by Equation or Equation. Positivity and convex-hull conjecture. The real weights are…
Let ([0,1]^2,lVert·rVert_2) be the unit square with the Euclidean metric. For a linear order ≤ on [0,1]^2, let OR_≤(n) denote its TSP order ratio function. Bertsimas–Grigni conjecture. For every linear order ≤ on the unit square, OR_≤(n)…
Given a finite point set P⊂R^2 with |P|=n, let T range over spanning trees on P, with each edge weighted by its Euclidean length. Define the dilation of T by δ(T)=max_p≠ q∈ Pd_T(p,q)/lVert p-qrVert_2, where d_T is the shortest-path…
Let P be a finite point set in a 2D CAT(0) complex with a single vertex O. Set H_0=P; for each i≥ 1, let H_i be obtained from H_i-1 by adding all intersections of shortest paths between pairs of points in H_i-1 with edges of the complex.…
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 continuous motion from its initial position to vertical. Rousseeuw and…