# Tag Info

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

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

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

### 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,626
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

### 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,626

### 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.6k
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 ...
• 903
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 ...
• 51.1k
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.2k
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
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,499

### 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 ...
• 12.2k
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
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,318

### 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,626
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,626
1 vote

### How to calculate complexity in a high dimensional space?

As far as I have understood, you aim to develop a framework to capture the hardness of combinatorial problems in 3D. However, there are major problems in your question. Your first sentence lacks a ...
• 93
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,036
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,909
1 vote

• 12.2k
1 vote

### How to continue this algorithm?

A conceptually far simpler algorithm is to try all the options. Cut the rectangle into $g=gcd(w,\ell)$ squares. There are finitely many ways to portion these squares into non-overlapping blocks that ...
• 1,046

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