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 ...
- 9,596
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,788
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,772
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 ...
- 23.1k
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 ...
- 50.9k
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 ...
- 36.9k
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,772
5
votes
Accepted
Is minimum knot crossing number elementary recursive?
The number of graphs on $n$ vertices is
$$2^{\frac{n(n-1)}{2}}.$$
The number of embeddings of a degree 4 planar graph with $n$ vertices is at most $6^n$. (If you know the clockwise order of the ...
- 24.3k
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,772
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 ...
- 9,595
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 ...
- 50.9k
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
- 50.9k
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 ...
- 9,596
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 ...
- 9,596
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 ...
- 146
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.3k
3
votes
Accepted
Unclear proof step in Feder and Greene's 1988 paper showing NP-Hardness of approximating k-center problem within a factor of 1.82
It just so happened that we used a similar reduction as part of our proof for NP-hardness of regret-minimizing set, so I'm pretty familiar with this. We have the following claim:
Let $V$ and $V'$ be ...
- 723
2
votes
Accepted
Intersection graphs of squares and rectangles
See "Squarability of rectangle arrangements", Konečný, Kučera, Opler, Sosnovec, Šimsa, and Töpfer, CCCG 2016. In particular their Theorem 6 proves for all $d$ the existence of graphs with boxicity 2 ...
- 50.9k
2
votes
Accepted
Finding a cell in an arrangement of simplices
If I am understanding your problem correctly, this is the problem of computing the face containing a given point in an arrangement of line segments. There is a randomized algorithm running in expected ...
- 18.1k
2
votes
Accepted
Reference needed for lower bound on number of guards in three-dimensional art gallery guarding
To my knowledge, Seidel's construction has only been published in O'Rourke's book and nowhere else.
In one of his papers, Seidel even refers to O'Rourke's book for a description of his own ...
- 5,772
2
votes
Accepted
Data structure for radial orderings of points on the plane
This problem is the same as halfspace range counting up to polylog factors.
Halfspace range counting in 2D
Preprocess $n$ points $S$ on the plane. A query takes a halfspace $H$ (represented ...
- 4,367
2
votes
Select circle with given radius that contains most points
Your algorithm is correct. If the best circle contains one point, your post-processing step will find it. If the best circle contains two or more points, then there is a way to shift it around so it ...
- 11.7k
2
votes
Accepted
Data structures for embedded simplicial complexes
First you can read the CGAL documentation that can help you to understand combinatorial and generalized maps, since it provide several examples. You can also read the book "Combinatorial Maps: ...
- 136
2
votes
Accepted
Example of Delaunay Triangulation where it does not minimize the maximum angle
This animation from the wikipedia article on delaunay triangulations shows you an example of where the delaunay triangulation will switch from having a horizontal interior edge to a vertical interior ...
- 1,276
2
votes
Find a boundary from set of 3d line segments
For each segment extract the two endpoints (remembering which segment they came from), now sort the endpoints by (say) lexicographical ordering. Any two endpoints that are the same are now adjacent. ...
- 9,596
2
votes
Accepted
Binary Trees for Nearest Neighbor Search
This essentially can be derived from a compressed quadtree representing approximate Voronoi diagrams. If you want the decision tree to be balanced you have to use a finger tree on the compressed ...
- 9,596
1
vote
Accepted
How to choose good diagonals when partitioning an orthogonal polygon into rectangles?
Starting with 5,7,$f$ and $g$ is correct. In order to complete the maximum independent you can proceed as follows. First, delete the vertices that are reachable from an unmatched vertex via an ...
- 1,026
1
vote
Embedding a n-tree into a b-dimensional space
This is not possible if the dimension $m$ is fixed. Consider a complete $b$-ary tree, in which all edges are oriented from the root $r$. Then all vertices lie in a ball of radius $h$ around $v_r$. On ...
- 3,899
1
vote
Data structure for radial orderings of points on the plane
One approach would be to use a k-d tree. You can use the k-d tree to answer the following query:
Count($x$, $\theta$):
Input: $x \in S$, $0 \le \theta < 2\pi$.
Output: The number of points $y \...
- 11.7k
1
vote
Accepted
Inclusion probability of irregularly shaped polygon
The first thing to notice is that an $n$-vertex polygon polygon $B$ is inside circle $A$ if and only if all of the vertices of $B$ are inside $A$. (1)
So the solution to your problem is exactly the ...
- 1,685
Only top scored, non community-wiki answers of a minimum length are eligible