Mathematics Problem Archive

Given a sorted list of $n$ real numbers, find for every $1\le k\le n$ the shortest interval containing exactly $k$ entries. Find a subquadratic algori...

Given lines in the plane and two vertices $s,t$ of their arrangement, find a subquadratic algorithm for the shortest $s$-$t$ path along arrangement ed...

Is there a near-linear-time algorithm to construct the straight skeleton of a simple polygon? Determine the optimal complexity, including for polygons...

Given motorcycles moving simultaneously along fixed rays and crashing upon reaching another track, determine the motorcycle graph in near-linear time....

Determine the optimal complexity of computing the volume of the union of axis-aligned boxes in fixed dimension at least three. In particular, is there...

Given a planar point set $P$, sample uniformly from the simple polygons with vertex set $P$ in polynomial time, or determine the complexity of countin...

Develop exact polynomial-time algorithms for the constructive forms of Aleksandrov's, Cauchy's, Minkowski's, Steinitz's, and Koebe's polytope-realizat...

On a centrally symmetric convex body, must every pair of points at maximum intrinsic surface distance be antipodal? Resolve this even for rectangular ...

Can every convex polytope be triangulated so that every vertex degree, or every edge degree, is bounded by a constant or by a polylogarithmic function...

Determine the least number of colors needed to color the Euclidean plane so that points at unit distance receive different colors....

Given a finite planar point set and a prescribed rectangle, approximate efficiently the minimum number of congruent copies of the rectangle needed to ...

Determine the minimum number of $d$-simplices needed to triangulate the $d$-dimensional cube, and its asymptotic growth with $d$....

Does the hyperbolic plane admit a smooth isometric immersion into $\mathbb R^4$? More generally, determine the least Euclidean dimension for such an i...

Are the Hermite constants associated with densest lattice sphere packings always rational? Determine their arithmetic nature in dimensions where the e...

Do there exist seven planar points in general position—no three collinear and no four concyclic—such that every pairwise distance is an integer?...

Given a polygonal room with perfectly reflecting sides and a point light source, characterize when every point of the room is illuminated. In particul...

Can the $3\times6$ rectangle with a $2\times2$ corner removed tile a rectangle using an odd number of congruent copies?...

What is the largest possible ratio between the sum of edge lengths of a tetrahedron that can pass through or fit inside another tetrahedron and the su...

Does there exist a nondegenerate triangle whose side lengths, three medians, three altitudes, and area are all rational?...

Can sums of square roots of integers be compared in polynomial time on a Turing machine? Equivalently, obtain effective polynomial bit bounds for a no...

For every positive integer $k$, let $R_k$ be a $1/k$ by $1/(k+1)$ rectangle. Can the entire collection $(R_k)_{k\ge1}$ be packed without overlap into ...

Find the largest function $t(n)$ such that every convex $n$-gon has a triangulation containing at least $t(n)$ distinct triangle areas; also determine...

Let $(X,\rho)$ be a finite metric space. Its fundamental polytope $R_{X,\rho}$ is the convex hull of the vectors $e_{x,y}=(\delta_x-\delta_y)/\rho(x,y...

Do there exist two irreducible algebraic curves of degrees $n$ and $m$, with $n+m>4$, each having an oval, for which the Poncelet map is well defined ...

Let $\gamma=\{x^2+y^2-1=0\}$ and $\Gamma_\varepsilon=\{p_2(x,y)+\varepsilon p_m(x,y)=0\}$, where $\Gamma_0$ is an ellipse surrounding $\gamma$, the cu...

On a regular dodecahedron, unfold a geodesic beginning at a vertex $v$ through successive faces. Call it short if it ends at a vertex and meets no ver...

What is the combinatorial complexity of the Voronoi diagram of a set of lines (or line segments) in three dimensions?...

What is the complexity of computing a minimum-cost Euclidean matching for $2n$ points in the plane? The cost of a matching is the total length of the ...

Can the class of 3SUM hard problems be solved in subquadratic time? These problems can be reduced from the problem of determining whether, given three...

What is the best output-sensitive convex hull algorithm for $n$ points in $\mathbb{R}^d$?...

Can the number of simple polygonalizations of a set of $n$ points in the plane be computed in polynomial time? A simple polygonalization is a simple p...

Can a minimum-link path among polygonal obstacles be found in subquadratic time?...

How many $\pi$-floodlights are always sufficient to illuminate any polygon of $n$ vertices, with at most one floodlight placed at each vertex? An $\al...

Can an $n$-vertex polygonal curve be simplified in time nearly linear in $n$?...

How efficiently can one compute a polyhedral surface that is an $\epsilon$-approximation of a given triangulated surface in $\mathbb{R}^3$?...

Given a sufficiently dense sample of points on a surface (technically, an $\epsilon$-sample), reconstruct a surface homeomorphic to the original....

Can the interior of every simply connected polyhedron whose surface is meshed by an even number of quadrilaterals be partitioned into a hexahedral mes...

Is it possible to trap all the light from one point source by a finite collection of two-sided disjoint segment mirrors? A light ray is trapped if it ...

An optimization problem that naturally arises in the study of ``swarm robotics'' is to wake up a set of ``asleep'' robots, starting with only one ``aw...

Consider a polyhedron with simply connected facets (no holes on a facet) and without boundary (every edge is incident to exactly two facets). Can the ...

Can every closed polyhedron be cut along its surface and unfolded into one piece in the plane without overlap? Such an unfolding is called a general u...

What is the complexity of finding a tour of maximum Euclidean length for a planar point set?...

What is the complexity of finding a shortest tour in a solid planar grid graph? A planar grid graph is a graph whose vertices are any set of points on...

What is the complexity of the pallet loading problem? Given two pairs of numbers, $(A,B)$ and $(a,b)$, and a number $n$, decide whether $n$ small rect...

What is the optimal partition of a square into convex pieces such that the circularity of the pieces is optimized? The circularity of a polygon is the...

Given an arbitrary polygon, transform it by a finite sequence of ``vertex-centroid'' moves to a regular polygon. A vertex-centroid move is a translati...

Let $C$ be a convex piece of paper; its boundary may be a smooth curve, or a polygon. A perimeter halving folding is a folding of $C$ obtained by iden...

Is there any genus-zero orthogonal polyhedron $P$ built by gluing together cubes face-to-face that cannot be edge-unfolded, where all cube edges on th...

Let $\rho(S)$ be the fewest number of reflex vertices in a polygonization of a 2D point set $S$, i.e., the fewest reflexivities of any simple polygon ...

Let $M$ be a closed polyhedral surface homeomorphic to $S^2$ which is entirely composed of equal regular pentagons. If $M$ is immersed in 3-space, is ...