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

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

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

Community wiki

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

#### Related Tags

computational-geometry × 491mg.metric-geometry × 162

discrete-geometry × 144

algorithms × 67

ag.algebraic-geometry × 50

convex-geometry × 46

convex-polytopes × 44

co.combinatorics × 38

reference-request × 36

graph-theory × 32

plane-geometry × 25

computational-complexity × 22

polygons × 21

dg.differential-geometry × 18

euclidean-geometry × 16

computer-algebra × 16

at.algebraic-topology × 14

polynomials × 14

oc.optimization-and-control × 14

polyhedra × 13

triangulations × 13

pr.probability × 11

linear-algebra × 11

linear-programming × 11

computational-topology × 10