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 ...
David Eppstein's user avatar
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$ ...
Gamow's user avatar
  • 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 ...
Jeffε's user avatar
  • 23.1k
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$. ...
Gamow's user avatar
  • 5,772
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 ...
Joshua Grochow's user avatar
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 ...
Peter Shor 's user avatar
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 ...
Gamow's user avatar
  • 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 ...
Neal Young's user avatar
  • 10.6k
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
David Eppstein's user avatar
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 ...
David Eppstein's user avatar
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 ...
Sariel Har-Peled's user avatar
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 ...
Sariel Har-Peled's user avatar
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 ...
Dan Feldman's user avatar
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 ...
Aryeh's user avatar
  • 10.5k
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 ...
Wei Zhan's user avatar
  • 828
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 ...
David Eppstein's user avatar
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 ...
Gamow's user avatar
  • 5,772
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 ...
Sasho Nikolov's user avatar
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: ...
gdamiand's user avatar
  • 136
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 ...
D.W.'s user avatar
  • 12.1k
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 ...
Chao Xu's user avatar
  • 4,439
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. ...
Sariel Har-Peled's user avatar
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 ...
JimN's user avatar
  • 1,316
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 ...
Sariel Har-Peled's user avatar
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 ...
Thomas Kalinowski's user avatar
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 ...
Yury's user avatar
  • 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 \...
D.W.'s user avatar
  • 12.1k
1 vote

Finding sets of heavily intersecting objects, while minimizing their size

If I understand right, you are interested in finite projective planes. These are the maximum combinatoric set systems in which all sets intersect each other exactly once. To briefly answer your ...
GMB's user avatar
  • 2,403
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 ...
SamM's user avatar
  • 1,685
1 vote

given a set of $n$ points in $d$-dimensional space and the basis vectors of some subspace, how to find all the points on that space?

One straightforward approach is to first compute a $d \times k-d$ matrix $M$ such that $Mx=0$ iff $x \in K$. Then you can determine which points from $A$ lie on $K$ by computing $Mx$ for each $x \in ...
D.W.'s user avatar
  • 12.1k

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