# Tag Info

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 ...
• 9,566

### 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$-...
• 50.3k

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

### 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, ...
• 9,566

### 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) ...
• 9,566

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

• 1,156

### 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 ...
• 9,566
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
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 ...

### 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 ...
• 674
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

### 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 ...
• 9,566

### 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 ...
• 9,566
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
• 50.3k
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 ...
• 50.3k
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 ...