# Tag Info

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
Accepted

### Acute triangles in "obtuse" polygons?

Take a very obtuse isosceles triangle and chop its acute angles.
• 40.5k
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, ...
• 468

### 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 ...
• 2,726

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

### 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 ...
• 143k
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 ...
• 146k
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 ...
• 102k
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

### 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....
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/...
• 13.2k
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 ...
• 102k
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 ...
• 158k

### 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$ ...
• 4,318

### 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 "...
• 146k
Accepted

• 19.9k