11 votes
Accepted

Does Approx Carathéodory's theorem implies dimensionality reduction

The approximate Caratheodory theorem goes back to the 60s, and probably way earlier than that (it follows for example from the mistake bound of the preceptron algorithm analysis). As for the ...
user avatar
9 votes

Would a purely topological computational model be useful in decision problems in topology?

Avishy Carmi and Daniel Moskovich have been developing tangle machines very recently, which is a topological model to describe information. There are two papers on the arXiv, as well as three ...
user avatar
  • 824
8 votes

Vertices of a polytope

No. Suppose all $a_i$'s are $0$ and all your $b_i$'s are equal; then the polytopes you can get by varying the $b_i$'s are essentially the hypersimplices. But the number of vertices of an $n$-...
user avatar
8 votes
Accepted

Would a purely topological computational model be useful in decision problems in topology?

I'm not sure whether this qualifies as a purely topological computational model, but there is a topological approach to anyonic quantum computation within the framework of which Aharonov-Jones-Landau ...
user avatar
7 votes

Voronoi Diagram of Lines

In 2010 Hemmer et al. gave an exact algorithm for the Voronoi diagram of lines in $\mathbb{R}^3$. In their introduction, they state that the $\Omega(n^2)$ lower bound and $O(n^{3+\varepsilon})$ upper ...
user avatar
  • 4,493
6 votes

Minimum equidecomposable decomposition

For disconnected one-dimensional regions with integer coordinates, equidecomposition into a minimum number of pieces is strongly NP-hard via an easy reduction to 3SUM: if one shape has segments whose ...
user avatar
6 votes

Coreset and VC dimension

Samples provides you only with statistical guarantees. For a fixed $\epsilon$ whatever you compute would hold for everything "except" $(1-\epsilon)$ fraction (I am being very informal here). Thus, ...
user avatar
6 votes

Largest cell in an arrangement

Somehow doing better than $O(n^d)$ looks hard. If the cell is significantly larger than its average expected size, one can use sampling, to find it. Formally, assume the bounded cells (in the plane) ...
user avatar
6 votes
Accepted

maximizing inner product

For three-dimensional vectors, construct the three-dimensional convex hull of the vectors in $L'$ in time $O(n\log n)$. The maximizer for a vector $v$ in $L$ is the point of the convex hull that is ...
user avatar
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 ...
user avatar
  • 22.8k
6 votes
Accepted

Minimal number of hyperplanes needed to separate sets of points from one other set

Your problem is NP-complete, even in the following two highly restricted cases: The dimension $d$ is part of the input, and the question is whether you can separate set $B$ from set $G$ by $k=2$ ...
user avatar
  • 5,712
5 votes
Accepted

Compute lowest dimensional polytope from a given set of sign vectors

This is equivalent to computing the sign rank of a matrix, which is NP-hard as shown in this paper. So you cannot expect too efficient of an algorithm.
user avatar
5 votes
Accepted

Maximum number of geometrically disjoint paths - is the complexity known?

The following paper establishes NP-hardness of essentially all non-trivial questions in this direction: Jan Kratochvíl, Anna Lubiw, Jaroslav Nesetril: Noncrossing Subgraphs in Topological Layouts....
user avatar
  • 5,712
5 votes
Accepted

Fast high-dimensional K-nearest neighbors

For high-dimensional exact nearest neighbor search the theoretical guarantees are pretty dismal: the best algorithms are based on fast matrix multiplication and have running time of the form $O(N^2D^\...
user avatar
5 votes
Accepted

Generalization of Beck's theorem

If you are asking if the same statement holds true or not in higher dimensions, it does. Just project all the points to a random 2-dimensional plane. Another natural generalization is to consider ...
user avatar
  • 6,940
5 votes
Accepted

Finding a point outside of each of a set of polygons in a bounded space

If the polygons can overlap, the problem can be solved in $O(n^2)$ time (where $n$ is the number of sides of the polygons in total) by constructing the arrangement of line segments and maintaining as ...
user avatar
5 votes

Complexity of testing if two sets of $m$ points in $\mathbb{R}^n$ differ only by rotation?

I think this is open. Note that if instead of testing equivalence under rotations you ask for equivalence under the general linear group, then already testing equivalence of degree three polynomials ...
user avatar
5 votes
Accepted

Complexity of computing the union of H-polytopes in three dimensions

Your problem is solvable in polynomial time, as the dimension is fixed (at $d=3$): Let $h_1,\ldots,h_n$ be an enumeration of all the bounding hyperplanes of the polytopes $P_1,\ldots,P_k$ and $Q$. ...
user avatar
  • 5,712
4 votes
Accepted

maximum weighted 2D coverage problem by a rectangle

Let me describe first how to solve this problem without precomputation, then I'll describe how to make use of precomputation. I'll focus on the unweighted case (each point has weight 1); all the ...
user avatar
  • 10.3k
4 votes

Fast high-dimensional K-nearest neighbors

Several state of the art approximate nearest neighbor methods in high dimensions are based on reducing the dimension of the space through randomized techniques. The main idea is that you can exploit ...
user avatar
4 votes
Accepted

Complexity for single-linkage clustering with max norm

Single-linkage clustering gives the same connections in the same order that you would find using Kruskal's algorithm for the minimum spanning tree, and the clustering can be found by finding a minimum ...
user avatar
4 votes

A least sized partition of a set under a distance metric

Ken Supowit proved that the following problem is NP-hard: Given a set $P$ of $n$ points in the Euclidean plane and an integer $k$, partition $P$ into $k$ clusters so that the largest cluster diameter ...
user avatar
  • 5,712
4 votes
Accepted

Finding planes from their points

Here's a quasi-polynomial-time algorithm, which doesn't fully answer the question but may give ideas and shows that the problem is unlikely to be NP-hard. This is for the variant where $d$ is given as ...
user avatar
  • 8,133
3 votes

H-representation of convex hull

If you're okay with additional variables, then the answer is yes. This follows from Balas's extended formulation for the disjunction of polyhedra. It shows that $\operatorname{convex}.\operatorname{...
user avatar
3 votes
Accepted

Coreset and VC dimension

The answer of Har-Peled is mainly regarding problems where you wish to cover points by shapes (e.g. balls). A strong relation to eps-nets and hitting sets can be found e.g. in his paper here For the ...
user avatar
3 votes
Accepted

Emptiness of complement of subspace arrangement

Your problem is coNP-hard. Take a 3SAT instance with variables $X$ and clause set $C$. Set the dimension in your problem to $n:=|X|$. For every clause $c\in C$, introduce a corresponding $(n-3)$-...
user avatar
  • 5,712
3 votes

Implementation of partition trees?

By the definition in the linked paper on page 5, the statement is wrong. Binary space partition (BSP) trees have been used for decades on computer graphics to speed up spatial queries, as have ...
user avatar
3 votes
Accepted

Approximating the value of k in $k$-mean clustering problem

This problem is known as Geometric Set Cover (which deals with covering with different shapes, so unit balls are a special case). I'm unaware of any relation to $k$-means which is a clustering ...
user avatar
  • 9,348
3 votes

A continuous center point of a convex spherical polygon

For your second question... For any distribution, if you take a sample $R$ of size $O(1/epsilon^2 )$ of it, and compute its center point, it is going to be a $\geq (1/3-\epsilon)$-center point, with ...
user avatar
3 votes

Voronoi Diagram of Lines

The problem is still open, although some progress was made on related problems (see http://arxiv.org/abs/1312.2194). It is known that if you are willing to use an approximate metric then the upper ...
user avatar

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