# Tag Info

### Smallest axis-aligned box that contains $k$ points

For $n$ points there are $O(n^3)$ empty boxes, see introduction of this paper http://www.cs.uwm.edu/faculty/ad/maximal.pdf. One can compute these boxes in roughly this time (see intro for refs). For ...
• 9,626

### Complexity of Unknotting problems

Such a quasi-polynomial algorithm has just been claimed by Marc Lackenby from Oxford University. He will present in next Tuesday (02 Feb 2021) in a Zoom talk: https://www.math.ucdavis.edu/research/...
• 8,903

### Super Mario Galaxy problem

This problem is very very difficult. We could simplify it to make it easier, as follows. We can add the assumption that the angle sum about every vertex of the polytope $P$ is a rational multiple of ...
• 613
Accepted

### Document references describing weaknesses for cutting planes and algebraic proof system?

For each of these proof systems we know that there are some formulas where the shortest proof needs to have exponential length. Some of the earliest examples are an exponential lower bound for the ...
Accepted

• 46
1 vote

### Separation of a preprocessed polyhedron and a plane

In case somebody would still be interested by the question: the snag in the Dobkin Kirpatrick explanation has also been pointed out in Barba and Langerman's Optimal detection of intersections between ...
• 1,095
1 vote

### What is the problem in "closest pair problem" if all points share the same x-coordinate

Without the assumption that no points share the same x-coordinate, we run into one of two problems: One problem occurs if you partition the space by x-coordinate. Say all points have the same x-...
• 111
1 vote

### Examples where insight from geometry was useful for solving something completely non-geometric

The Necklace splitting problem is a very nice example. Its statement is purely combinatorial: assume that you have an open necklace with beads of $k$ different colours, and the number of beads of each ...

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