Mathematics Problem Archive

Extend Thurston's finite combinatorial classification from critically finite rational maps to all geometrically finite rational maps: give finite topo...

If a complete hyperbolic $3$-manifold $N$ has fundamental group generated by $n$ elements, is there a bound $R_n$, depending only on $n$, on the radiu...

For $n>1$, do there exist nontrivial critically finite rational maps $f:\mathbb P^n\to\mathbb P^n$ whose postcritical hypersurface $V$ has Kobayashi-h...

Let $A$ be a hyperbolic attractor of a diffeomorphism of a compact $3$-manifold. Beyond the known Anosov, laminated, Williams, and invariant-torus cas...

Given an explicitly specified smooth orientation-preserving diffeomorphism $F$ of the $2$-sphere, is its topological entropy Turing-computable to arbi...

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 the union of ``fat'' objects in $\mathbb{R}^3$?...

Can the Euclidean minimum spanning tree (MST) of $n$ points in $\mathbb{R}^d$ be computed in time close to the lower bound of $\Omega(n \log n)$?...

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

What is the maximum number of $k$-sets? (Equivalently, what is the maximum complexity of a $k$-level in an arrangement of hyperplanes?)...

Is there a deterministic, linear-time polygon triangulation algorithm significantly simpler than that of Chazelle?...

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

Is there an $O(n)$-space data structure that supports $O(\log n)$-time point-location queries in a three-dimensional subdivision of $n$ faces?...

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

Given a visibility graph $G$ and a Hamiltonian circuit $C$, determine in polynomial time whether there is a simple polygon whose vertex visibility gra...

What is the complexity of the vertical decomposition of $n$ surfaces in $\mathbb{R}^d$, $d \ge 5$?...

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 the flip graph connected for general-position points in $\mathbb{R}^3$? Given a set of $n$ points in $\mathbb{R}^3$, the flip graph has a node for ...

Can every convex polytope in $\mathbb{R}^3$ be partitioned into tetrahedra such that the dual graph has a Hamiltonian path?...

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

How many intersections among an arrangement of pseudosegments in the plane must be added as vertices to allow the pseudosegment arrangment to be exten...

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

How many polyominoes on $n$ squares are there? A polyomino is a connected interior-disjoint union of axis-aligned unit squares joined edge-to-edge, in...

Is it true that every two sets of $n$ planar points in general position with the same number points on their convex hulls have compatible triangulatio...

For a point set $P$ in $\mathbb{R}^d$, let $f_d(P)$ be the number of unit-distance point pairs: $$f_d(P) = \left| \{ (u,v) \mid u, v \in P, \, \|u-v\|...

For a planar point set $S$, is the number of pointed pseudotriangulations always at least the number of triangulations? A pseudotriangle is a planar p...

Given two sets of numbers, each of size $n$, how quickly can the set of all pairwise sums be sorted? In symbols, given two sets $X$ and $Y$, our goal ...

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

Does every simple graph with maximum vertex degree $\Delta \leq 6$ have a 3D orthogonal point-drawing with no more than two bends per edge? A 3D ortho...

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

Does every $n$-vertex planar graph have a 3D grid drawing with $O(n)$ volume? A 3D grid drawing of a graph is a placement of the vertices at distinct ...

Does every planar graph have $O(1)$ queue-number? A queue layout of a graph consists of a linear order of the vertices and a partition of the edges in...

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

For any (planar) triangle $T$, is there is a $3$-coloring of the (infinite) plane with no monochromatic copy of $T$? We imagine congruent copies of $T...

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

Given a set of $n$ unit-radius balls in $\mathbb{R}^3$, what is the number of lines that are tangent to four of the balls in the set, and miss all the...

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 a data structure maintaining a set of $n$ points in the plane subject to insertions, deletions, and nearest-neighbor queries in $O(\log n)$ t...

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

Label the faces of a unit cube with numbers $1$--$6$ as in a die. Place the cube to sit on an integer lattice grid, with one corner at the origin and ...