Mathematics Problem Archive

Given $n$ points and $m$ hyperplanes in $\mathbb R^d$ whose incidence graph contains no $K_{s,t}$, determine the maximum number of incidences. Of spec...

For an $n$-point planar set, determine the maximum number of halving lines. More generally, determine the maximum number of $k$-sets, subsets obtained...

For $n$ pseudocircles in general position, determine the maximum number of tangent pairs and the maximum number of digon cells. Determine whether the ...

Determine the worst-case complexity of the medial surface and of an offset surface of an $n$-feature polyhedron, and of the Voronoi diagram of $n$ lin...

Determine the exact Erdős–Szekeres number $f(n)$, the least number of planar points in general position forcing a convex $n$-gon. Also determine sharp...

Determine the combinatorial complexity of the visibility complex of $n$ pairwise disjoint unit spheres in three-dimensional space....

Given $n$ planar points, find a subquadratic algorithm for the minimum-area triangle or prove a quadratic lower bound in a suitable computation model....

Given $n$ points in $\mathbb C^2$, determine in quadratic time whether three lie on a complex line, or prove a quadratic lower bound; the known algori...

For fixed $d>3$, determine whether every point of an $n$-point set in $\mathbb R^d$ is a convex-hull vertex faster than the best known near-$n^{2\lflo...

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...

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...

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 ...

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 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 ...

Partition a given polygon $P$ into $n$ mutually congruent pieces so that the area of $P$ not covered by the union of the pieces is as small as possibl...

Identify or construct all $k$-equiprojective polyhedra. A polyhedron $P$ is $k$-equiprojective if its orthogonal projection to a plane is a $k$-gon in...

Does every convex polyhedron $P$ have a zipper unfolding? A zipper unfolding cuts open $P$ via a single path, necessarily a Hamiltonian path (to span ...

Do there exist rectangles that may be partitioned into a finite number $n$ of rectangular pieces of equal area but with all perimeters different?...

Is there a stable cluster of bubbles in $\mathbb{R}^3$ in which some bubble is topologically a torus?...