# Tag Info

## Hot answers tagged computational-geometry

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,787
Accepted

### Acute triangles in "obtuse" polygons?

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

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

### 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 ...
• 152k
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 ...
• 106k

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

• 106k
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 ...
• 180k
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 ...
• 4,112

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

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

• 5,394
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 ...
• 149k