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.

- 40.5k

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

- 468

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

- 2,726

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

- 143k

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

- 146k

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

- 102k

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

- 111

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

- 13.2k

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

- 102k

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

- 158k

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

- 4,318

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

- 146k

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

- 1,545

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

- 186

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

- 40.5k

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

- 661

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

- 35k

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

- 146k

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

- 19.9k

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

- 146k

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

- 19.9k

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

- 616

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

#### Related Tags

computational-geometry × 432mg.metric-geometry × 145

discrete-geometry × 109

algorithms × 63

ag.algebraic-geometry × 45

convex-polytopes × 43

convex-geometry × 42

reference-request × 35

co.combinatorics × 30

graph-theory × 27

plane-geometry × 24

computational-complexity × 21

polygons × 21

dg.differential-geometry × 18

euclidean-geometry × 15

computer-algebra × 15

polynomials × 13

oc.optimization-and-control × 13

polyhedra × 13

at.algebraic-topology × 12

triangulations × 12

linear-algebra × 11

linear-programming × 11

pr.probability × 9

ac.commutative-algebra × 8