Skip to main content
11 votes

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 ...
Sariel Har-Peled's user avatar
9 votes

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/...
Denis's user avatar
  • 8,903
9 votes

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 ...
Sam Nead's user avatar
  • 613
7 votes
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 ...
notautogenerated's user avatar
7 votes
Accepted

Proof for Upper Bound of Sum of Square Roots Problem

Here is a rather sloppy proof sketch. Let $S = \sum_{i=1}^n \delta_i \sqrt{a_i}$ where $\delta_i \in \{\pm 1\}$. This is an algebraic number of degree at most $2^n$ and height at most $H = (max(a_i))^{...
Nikhil's user avatar
  • 1,364
6 votes
Accepted

Minimizing $L_2$ norm of a vector with two distinct entries

(This is probably a comment but I cannot comment) This seems to be 1-dimensional $k$-means clustering for $k=2$ and $k=4$. Here is a reference that gives a $O(kn + n \log n)$ algorithm for 1-d $k$-...
xmq's user avatar
  • 191
6 votes

Reference request: Shortest homotopic curve via vertex releases

This is morally equivalent to a slower variant of the Hershberger-Snoeyink funnel algorithm. I'm not aware of any exposition of your simple algorithm in the literature. This is actually a little ...
Jeffε's user avatar
  • 23.2k
4 votes
Accepted

Citation for isometric embeddability of $\ell_2$ into $\ell_p^\binom{n}{2}$ for $p \geq 1$?

This paper by Keith Ball seems to be what you are looking for: Ball, Keith. "Isometric embedding in $\ell_p$-spaces." European Journal of Combinatorics 11.4 (1990): 305-311. Link to the paper ...
Cyrus Rashtchian's user avatar
4 votes
Accepted

Status of certain problems in knot theory

To complete the first answer, the equivalence problem is decidable (this dates back to haken, a good reference is Lackenby's survey Elementary Knot Theory ). It is neither known to be in NP nor known ...
Arnaud's user avatar
  • 834
4 votes

Status of certain problems in knot theory

Regarding the HOMPFLY-PT polynomial, evaluating the coefficients of the Jones polynomial is #P-hard, and this of course transfers to the more general HOMPFLY-PT polynomial: https://doi.org/10.1017/...
Hermann Gruber's user avatar
4 votes

Partitioning a connected polygon into connected pieces of equal area

To complement Sariel's answer, some closely related problems are hard. In particular, for a non-convex polygon, it's NP-hard to find a partition into two pieces of equal area while minimizing the ...
David Eppstein's user avatar
3 votes
Accepted

Partitioning a connected polygon into connected pieces of equal area

There must be many ways to do it - here is one way... Compute the medial axis of the polygon using the $L_1$ metric. Any point on the boundary defines a natural segment that goes from this point to a ...
Sariel Har-Peled's user avatar
3 votes

Complexity of Unknotting problems

The outline from Marc Lackenby's talk about a quasipolynomial algorithm for Unknottedness. Unknot recognition in quasipolynomial time outline.. Under the talks section there are slides about the ...
user3483902's user avatar
  • 1,261
3 votes

VC dimension of intersection of half-spaces

It has been recently shown by Csikos, Kupavskii, Mustafa in "Optimal Bounds on the VC-dimension" that the VC dimension of $k$-fold unions (or intersections or XORs) of half-spaces in $R^d$ ...
Aryeh's user avatar
  • 10.6k
2 votes

What is the proof that visibility graphs can be used to compute the shortest path?

I think the first proof was given in Der-Tsai's 1978 thesis on pages 111-113. With the above result it is immediate to realize that the shortest path problem with line segments as obstacles can ...
saul.shanabrook's user avatar
2 votes
Accepted

Complexity of polygon intersection test

TL;DR: Yes, in principle this can be done in $O(n)$ and the book is inaccurate. This is quite subtle, the first statement is not correct. Returning all intersections has a $\Omega(n\log n)$ lower ...
user3508551's user avatar
  • 1,153
2 votes
Accepted

Complexity of existence of simple polygonalization with prescribed area?

The answer to your question is already contained in Fekete's paper. In Section 3, Fekete shows that the following problem GRID-EMPTY is NP-complete: Problem: GRID-EMPTY Instance: a set $S$ of $n$...
Gamow's user avatar
  • 5,772
1 vote
Accepted

partitioning points in the plane into two clusters to minimize maximum cluster diameter

Theorem 1. There is an $O(n\log n)$-time algorithm for the problem in the post. Proof. We first state two utility lemmas, for an arbitrary edge-weighted graph $G$. We postpone their proofs, which are ...
Neal Young's user avatar
  • 10.8k
1 vote

Is this a novel technique for determining whether or not two rotated rectangles collide?

If you rotate your rectangles through a common origin, then your method works. Your method works if there always exists a separating line that is parallel to a side of one of your rectangles. Such a ...
Tim's user avatar
  • 627
1 vote

VC-dimension of infinite set of triangle wave

First of all, presumably you want the VC-dimension of your class of composed with the sign function, which yields a class of Boolean functions (otherwise, VC-dim is not defined). With that out of the ...
Aryeh's user avatar
  • 10.6k
1 vote
Accepted

How hard is deciding the existence of a polygonization with prescribed perimeter?

Your problem is NP-hard, since it contains the Hamiltonian cycle problem on grid graphs as special case: Given a set of lattice points in the plane, is there a cycle in which all edges have lengths $1$...
Gamow's user avatar
  • 5,772
1 vote

How not to compute the smallest circle enclosing a finite set of circles

This step of removing $X$ from $L$ before continuing recursion actually improves the algorithm, because it removes the already-added $X$ from the pool of basis candidates. It will always, provably ...
Larry B.'s user avatar
  • 111
1 vote

BSP, but with curved surfaces (NURBS? kernelized support vectors?)

Just lift the points to higher dimensions, and use BSP in the higher dimensional space. This is a standard techniuqe - see linearization (in section 3 here: http://sarielhp.org/p/04/survey/survey.pdf)....
Sariel Har-Peled's user avatar
1 vote

BSP, but with curved surfaces (NURBS? kernelized support vectors?)

You can absolutely do it with kernelized support vectors. I don't have a publication handy but I've implemented it myself before. You'll probably want to use quadrics for the split planes, and ...
Kevin Daley's user avatar
1 vote
Accepted

VC dimension of Voronoi cells in R^d?

Please check Theorem 21.5, Section 21 in the book "A probabilistic Theory of Pattern Recognition (1996)" from Devroye, Gyorfi, and Lugosi. I think the following upper bound is valid: VC $\leq$ $k + (d+...
AlexGj's user avatar
  • 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 ...
Joseph Stack's user avatar
  • 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-...
Bladt's user avatar
  • 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