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

### 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 ...
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$ ...

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

### 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 ...
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$. ...
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 ...

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

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

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

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

### 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 ...
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: ...
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 ...

### 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. ...
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 ...
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 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 ...
1 vote

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 \... 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 ...

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