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 ...
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$-...
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 ...
  • 4,503
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 ...
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, ...
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) ...
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 ...
  • 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$ ...
  • 5,732
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.
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....
  • 5,732
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 ...
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^\...
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 ...
  • 6,950
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 ...
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$. ...
  • 5,732
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 ...
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 ...
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 ...
  • 5,732
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 ...
  • 8,461
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{...
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 ...
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)$-...
  • 5,732
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 ...
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 ...
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 ...
  • 9,378
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 ...
3 votes

Complexity of counting maximum number of co-linear points in Euclidean plane

First, my understanding is that the paper you linked to does not show that 3sum is incorrect. It just shows that the 3sum conjecture is false in a model of computation that is not realistic (i.e., we ...
3 votes
Accepted

The decision procedure of theory of closed real field is in NP-hard?

Yes, even in the purely existential case. See https://en.wikipedia.org/wiki/Existential_theory_of_the_reals
3 votes
Accepted

Convex polygons inclusion relation

Here's an argument that you need time quadratic in the number of polygons. More precisely, you should not be able to find containing pairs among $n$ $k$-sided polygons in time $O(n^{2-\epsilon})$, for ...
3 votes

VC dimension of the class of all polygons with k vertices

Assuming that the $k$-gon is simple (i.e., does not intersect itself and has no holes) and $k>3$, the two-ears theorem, https://en.wikipedia.org/wiki/Two_ears_theorem implies that it can be ...
  • 10.1k

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