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 ...
  • 6,535
24 votes
Accepted

Acute triangles in "obtuse" polygons?

Take a very obtuse isosceles triangle and chop its acute angles.
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, ...
16 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 ...
15 votes

Is every graph an edge-crossing graph?

The answer to 1 is no. To see this, note that every edge-crossing graph is a string graph. A string graph is a graph which is the intersection graph of arbitrary curves in the plane. However, there ...
  • 29.2k
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 ...
13 votes
Accepted

Given a set of 2D vertices, how to create a minimum-area polygon which contains all the given vertices?

I assume you intend the problem in which the polygon's vertices must be exactly the given set of points. If so, then, Yes, the problem is NP-hard: Fekete, Sándor P. "On simple polygonalizations ...
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 ...
12 votes
Accepted

Are all well behaved "mean" functions on $\mathbb{R}^+$ equivalent?

Define a mean algebra to be a set $S$ with an binary operation $M$ satisfying (1), (2), and (4). We can define $M(a,b,c,d)=M(M(a,b),M(c,d))$ and this will depend only on the multiset $\{a,b,c,d\}$. ...
  • 30.1k
11 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....
10 votes
Accepted

Computionally efficient vertex enumeration for (convex) polytopes

cddlib is rather old; a much more efficient implementation of the double description method is in PPL (Parma Polyhedra Library). One frontend to PPL can be found in Sagemath: http://www.sagemath.org/...
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 ...
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 ...
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$ ...
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 "...
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 $\#\...
  • 69.6k
8 votes

Is every graph an edge-crossing graph?

No, and you can see this from just a counting argument. For determining which of the $ n $ chords of the circle intersect, it is enough to know the order of the $ 2n $ endpoints on the circle. (You ...
8 votes

What are the applications of Voronoi diagrams in pure mathematics?

For topological combinatorics, Voronoi diagrams provide extremely nice configuration spaces. In particular, some mass partitioning problems can be tackled using this type of subdivision. Power ...
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 ...
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/...
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, ...
  • 2,324
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 ...
  • 1,482
7 votes
Accepted

Is every graph an edge-crossing graph?

Such graphs are called "circle graphs" and if you search on that phrase you will find some literature. For example, some is around page 56 in this book. Figure 2 in this paper shows a 7-vertex graph ...
7 votes

algebraic topology and 3d/4d printing

There are certainly many "digital artists" who are inspired by topology in their 3D-print designs. E.g., Torolf Sauermann:                      ...
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 ...
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 ...
6 votes
Accepted

Angle subtended by the shortest segment that bisects the area of a convex polygon

$\let\eps\varepsilon$This is not a complete answer. I will just show that $\theta$ can be smaller than $\pi/3$, but $\theta>\pi/4$. 1. Take an isosceles triangle $XYZ$ with $\angle Y=\angle Z=\pi/...
6 votes

algebraic topology and 3d/4d printing

I think one excellent 4d printing project that (to my knowledge) nobody has done yet would be to print the Optiverse. This is John Sullivan's minimal elastic bending energy version of the $\mathbb RP^...
  • 41.3k
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, -...
  • 3,502
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 ...

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