Skip to main content
30 votes
Accepted

Why did Robertson and Seymour call their breakthrough result a "red herring"?

Seymour and Robertson have indeed said that, and in fact they wrote that in their 2003 article in which they published the graph structure theorem. Here is the quote from Robertson and Seymour „Graph ...
Claus's user avatar
  • 6,787
24 votes
Accepted

Acute triangles in "obtuse" polygons?

Take a very obtuse isosceles triangle and chop its acute angles.
Anton Petrunin's user avatar
23 votes
Accepted

Can squares of side 1/2, 1/3, 1/4, … be packed into three quarters of a unit square?

The standard simple proof that $\sum_{n=1}^\infty \frac1{n^2}$ converges is to round each $n$ down to the nearest $2^k$; this rounds each $\frac1{n^2}$ up to the nearest $\frac1{2^{2k}}$. In fact, ...
Jeff Egger's user avatar
22 votes
Accepted

(non-)existence of the aperiodic monotile

This recent preprint claims to find such a tile. David Smith, Joseph Samuel Myers, Craig S. Kaplan, Chaim Goodman-Strauss, “An aperiodic monotile”, (2023-03-20) arXiv:2303.10798 A longstanding open ...
15 votes

Can squares of side 1/2, 1/3, 1/4, … be packed into three quarters of a unit square?

Note: This answer is wrong. There are two problems: The claim of Lemma 1 should presumably be read in the context of the global assumption in Paulhus's paper that $w\leq l$. This assumption ...
Robin Houston's user avatar
15 votes

How many triangulations of a regular octahedron are there, without introducing new vertices?

No, these are all. The edge graph of the octahedron has no $K_4$ subgraph, so you have to add a new edge to make a triangulation. The only possible places for a new edge are connecting opposite ...
David E Speyer's user avatar
13 votes
Accepted

A quadratic $O(N)$ invariant equation for 4-index tensors

Well, this is not actually an answer to either of the OP's questions; at most, it provides an easier way to classify the solutions for the $n=3$ case, and that might point a way towards an analysis ...
Robert Bryant's user avatar
12 votes

Counting points above lines

This problem seeks to count incidences between n points and n halfplanes; it can be addressed as a halfplane range counting problem; see the recent paper by Chan and Zheng (https://arxiv.org/pdf/2111....
Joseph Mitchell's user avatar
12 votes
Accepted

Is the maximal packing density of identical circles in a circle always an algebraic number?

Yes indeed, they are all algebraic. The idea is that we can describe the critical $r$ as a first-order formula in the language of fields, something like $$\forall r_1\quad ((0 < r_1 \wedge r_1 \le ...
Aleksei Kulikov's user avatar
10 votes
Accepted

Characteristic polynomial of an $8 \times 8$ symmetric matrix with indeterminate entries related to octonionic multiplication

Let $a,b,c\in\mathbb{O}$ be octonions and consider the linear map $L:\mathbb{O}\to\mathbb{O}$ defined by $$ L(x) = (b(cx))a = R_aL_bL_c(x). $$ One desires a formula for the characteristic polynomial ...
Robert Bryant's user avatar
10 votes
Accepted

How to plot this fractal

The source info (War in the Age of Intelligent Machines) identifies the fractal as a Julia set, iterates of $z\mapsto z^2+z_0$. It has evidently been distorted (warped) to give it a 3D appearance. I ...
Carlo Beenakker's user avatar
10 votes
Accepted

Desargues ten point configuration $D_{10}$ in LaTeX

This example shows that $s\le 2$ and for this $s$, $c\le 3$. Note that we are lucky with the latter, because there is a configuration for which every combinatorially equivalent realization has at ...
Alex Ravsky's user avatar
  • 4,112
9 votes

The intersection of two $l_1$ balls

There is an exponential upper bound of $9^n$, since every vertex of $B_1 \cap B_2$ is the intersection of a $k$-face of $B_1$ and a $(n-k)$-face of $B_2$ for some $k$, and the $\ell_1$-ball has $3^n$ ...
Guillaume Aubrun's user avatar
9 votes

Check if a polygon has an axis of symmetry in $O(n)$ time

Indeed that paper I cited in the comments describes how to determine all symmetries of a polygon $P$ in $O(n)$ time. The polygon is first translated so that its centroid is at the origin. Then a "...
Joseph O'Rourke's user avatar
9 votes
Accepted

Complexity of counting regions in hyperplane arrangements

The problem is $\#\mathsf{P}$-complete. As you already noted, the problem is $\#\mathsf{P}$-hard even when we restrict to graphical arrangements, so it remains to show that the problem is in $\#\...
Timothy Chow's user avatar
  • 79.3k
8 votes

Does a minimum area disk that is bounded by a cycle $C$ continuously deform in $R^3$ as $C$ moves in $R^3$?

This is a standard question. Look at the following image from Morgan's "Geometric measure theory". It should convince you that the answer is no. The curve admits two area minimizing discs and it ...
Anton Petrunin's user avatar
8 votes
Accepted

Computer algebra for calculating curvature when the tensor metric is very big

Try SageManifolds http://sagemanifolds.obspm.fr/ See this example (there are several others) for how to compute the curvature tensor from the metric http://nbviewer.jupyter.org/github/sagemanifolds/...
Paul Bryan's user avatar
8 votes
Accepted

Is there an upper bound on the number of points in point cloud for which we compute the persistent homology?

It depends very much on the type of simplicial complex you're using. If you have points in 3d then doing Cech/Delaunay complex is feasible with millions of points. If you have high dimensional data, ...
alesia's user avatar
  • 2,582
7 votes

Are point sets of the same order type connected by continuous (order type)-preserving motion?

The answer is indeed No. The most economic example up to now i think is mentioned Suvorov's. Independently examples was constructed by P. Mani, B. Jaggi, B. Sturmfels, N. White "Uniform oriented ...
Nikolai Mnev's user avatar
  • 1,482
7 votes
Accepted

Intersections of quadratic planes as elliptic curves

Regarding your main question, this is done in Cassels, Lectures on elliptic curves, $\S$ 8 (iv) p. 36. We may assume that the common rational point of the quadrics is $(X:Y:Z:T)=(0:0:0:1)$. Then the ...
François Brunault's user avatar
7 votes
Accepted

Volume of a finite union of overlapping balls?

This impressive work was tested on ~60,000 models in the Protein Data Bank, computing the volume of the union of sometimes more than 50,000 atoms represented as balls of different radii. Implemented ...
Joseph O'Rourke's user avatar
7 votes

Aperiodic monotile in $\mathbb{R}$

It all depends on what one is willing to accept as a "tile". Bounded measurable set is out of question (if we use translations only, which the OP requested), so we have to drop either ...
fedja's user avatar
  • 60.2k
7 votes
Accepted

Writing a smooth plane quartic as the vanishing of $Q_0Q_2 - Q_1^2$ for quadratic $Q_0,Q_1,Q_2$

The condition on your coefficients is an underdetermined system of quadratic equations. So specializing some of them (for instance setting them $0$), you can try to get a system with a finite number ...
Peter Mueller's user avatar
6 votes

Reasons to prefer one large prime over another to approximate characteristic zero

I prefer primes like 1000003 and 1000000007 because it is easy to recognize small integers and rational numbers with small denominators in the output. For instance, modulo 1000003 we have 1/3=666669, -...
Anton Mellit's user avatar
  • 3,592
6 votes

Questions on Discrete Exterior Calculus in numerical computing

This response is a few years late, but I feel those questions are still relevant today. In the recent years new applications of DEC appeared in fields such as computer graphics, geometry processing, ...
E. Schulz's user avatar
  • 201
6 votes
Accepted

Convex caps with prescribed edges

No. A subdivision that can be lifted to a convex cap is called regular (or coherent, or weighted Delaunay). Here is an example of a non-regular subdivision: For more on this, I recommend the book "...
Ivan Izmestiev's user avatar
6 votes

Algorithm to compute the Voronoi diagram of points, line segments and triangles in $\mathbb{R}^3$

Voronoi diagrams of points in $R^3$ are now implemented in several software libraries and can be computed, for example, in a few lines of Python code. This has not always been the case, so it still ...
Iddo Hanniel's user avatar
6 votes

largest diameter of intersection of two balls

The best result that I know is that when $X$ simply-connected manifold with non-positive sectional curvature ($n \geq 2$), $q_X = \sqrt{3}$. This directly follows from a corollary of the Rauch ...
Gabe K's user avatar
  • 5,394
6 votes
Accepted

To minimize the Hausdorff distance between convex polygonal regions

A polynomial-time algorithm was presented in this paper: Chew, L. Paul, Michael T. Goodrich, Daniel P. Huttenlocher, Klara Kedem, Jon M. Kleinberg, and Dina Kravets. "Geometric pattern matching ...
Joseph O'Rourke's user avatar
6 votes
Accepted

Final project ideas - computational geometry

Although The Open Problems Project has grown a bit out-of-date, we recently moved it to github to improve updating. Because it was "originally aimed to record important open problems of interest ...
Joseph O'Rourke's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible