Mathematics Problem Archive

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

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

Is the Yao-Yao Graph a $t$-spanner for constant $t$? A geometric graph is a $t$-spanner (or just a spanner) if, for every pair of nodes, the shortest ...

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

Let us say that two rectangles in the place are independent if both their $x$- and $y$-axis projections are disjoint. A set of rectangles is then inde...

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

For $k\leq n+1$ and prescribed volumes in $\mathbb{R}^n$, prove that the standard $k$-bubble is uniquely area-minimizing. For $n=3$, are standard clus...

Is every bubble cluster in $\mathbb{R}^3$ made of spherical pieces meeting according to Plateau's rules necessarily stable, in the sense of having non...

Let $A_X(v_1,\ldots,v_k)$ be the area of a minimizing $k$-bubble of volumes $v_i$ in a Riemannian manifold $X$. For $X=\mathbb{R}^n$, is $A_X$ strictl...

Are all regions in every area-minimizing bubble cluster in $\mathbb{R}^n$ connected?...

Determine the shapes of minimizing clusters of immiscible fluids when different interfaces have different surface tensions, even for planar double bub...

Determine double crystals in $\mathbb{R}^3$ minimizing orientation-dependent surface energy for a cubic Wulff shape and for general Wulff shapes. Must...

Is a crystal resting on a table under gravity necessarily convex?...

Classify minimizing polyhedral soap-film cones in dimensions five through seven and in all higher dimensions....

Do nonpolyhedral minimizing soap-film cones exist in dimensions four through seven? Construct higher-dimensional examples using triple junctions which...

Let $k(n)$ be the maximum number of regions meeting at one point in an area-minimizing partition in $n$ dimensions. Determine the growth of $k(n)$ and...

Is the known list of boundary singularities of soap films in $\mathbb{R}^3$ complete? Classify what happens for singular or immersed boundaries and wh...

Determine the smallest density greater than one of a minimal cone in $\mathbb{R}^n$, with variants imposing area-minimizing or isolated-singularity hy...

Classify the singularities allowed in soap films in three-dimensional orbifolds, and more generally in cone manifolds....