# Tag Info

9

Avishy Carmi and Daniel Moskovich have been developing tangle machines very recently, which is a topological model to describe information. There are two papers on the arXiv, as well as three introductory posts on the blog "Low Dimensional Topology" : http://ldtopology.wordpress.com/2014/05/04/low-dimensional-topology-of-information/

9

This problem is known as the question of realizability of pseudoline arrangements by straight lines. An arrangement of pseudolines is an arrangement of $n$ curves in the plane, such that any two curves intersect exactly once. For pseudolines, you can define the same labeling as the OP does. Pseudoline arrangements are related to oriented matroids, and you ...

8

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$-dimensional hypersimplex can be any binomial coefficient $\binom{n}{k}$. In particular choosing $k=n/2$ gives an exponential number of extreme points.

8

I'm not sure whether this qualifies as a purely topological computational model, but there is a topological approach to anyonic quantum computation within the framework of which Aharonov-Jones-Landau and Freedman-Kitaev-Wang proved that a quantum computer can "additively" approximate the Jones polynomial at a root of unity in polynomial time. Furthermore, by ...

8

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 dimensionality reduction, the answer is no - the supporting subsets are different subsets, and their number is too large. In particular, the number of possible subsets ...

7

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 bound are still the best known on the combinatorial complexity of the resulting Voronoi diagram. Their algorithm runs in time $O(n^{3+\varepsilon})$, matching ...

6

For disconnected one-dimensional regions with integer coordinates, equidecomposition into a minimum number of pieces is strongly NP-hard via an easy reduction to 3SUM: if one shape has segments whose lengths are the 3SUM inputs and the other has segments whose lengths are the bins you have to pack them in, then you can do it with no additional cutting iff ...

6

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, taking an $\epsilon$-net sample of a set of points in the plane, computing its smallest enclosing disk, results in a disk $D$ that contains $(1-\epsilon)$ fraction ...

6

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) form a polygon of area $1$ (this polygon $Q$ can be computed in near linear time in the plane). Assume the largest bounded cell $C$ in the arrangement of lines ...

6

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 most extreme in the direction of $v$, and extreme-vertex queries may be answered in logarithmic time by using a Dobkin-Kirkpatrick hierarchy for the convex hull. ...

6

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 surprising, given how many times the basic funnel algorithm has been rediscovered [Tompa, STOC 1980; Chazelle, FOCS 1982; Lee and Preparata, Networks 1984; ...

5

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.

5

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. SIAM J. Discrete Math. 4(2): 223-244 (1991)

5

If you are asking if the same statement holds true or not in higher dimensions, it does. Just project all the points to a random 2-dimensional plane. Another natural generalization is to consider hyperplanes instead of lines. Here, you have Beck's "other" theorem: Theorem: For any $d \geq 2$, there are constants $\beta_d, \gamma_d \in (0,1/2]$ such that ...

5

For high-dimensional exact nearest neighbor search the theoretical guarantees are pretty dismal: the best algorithms are based on fast matrix multiplication and have running time of the form $O(N^2D^\alpha)$ for some $\alpha < 1$. On the other hand you can do better if you are ok with approximation. Locality sensitive hashing can be used to achieve ...

5

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 you construct it the number of polygons that cover each cell of the arrangement. There are $O(n^2)$ cells, arrangements can be constructed in $O(n^2)$ time, and ...

5

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 is GI-hard (Agrawal-Saxena STACS '06, author's freely available version), and in fact is at least as hard as testing isomorphism of algebras. Now, GI-hardness is ...

4

Hausdorff distance is what you are looking for.

4

Let me describe first how to solve this problem without precomputation, then I'll describe how to make use of precomputation. I'll focus on the unweighted case (each point has weight 1); all the ideas should extend to the weighted case straightforwardly. Here is an algorithm without precomputation: Use a sweep line. Think of sweeping a vertical line from ...

4

Single-linkage clustering gives the same connections in the same order that you would find using Kruskal's algorithm for the minimum spanning tree, and the clustering can be found by finding a minimum spanning tree and then running Kruskal's algorithm on the resulting $(n-1)$-edge graph. Therefore, the time is bounded by the MST construction + the time to ...

4

Several state of the art approximate nearest neighbor methods in high dimensions are based on reducing the dimension of the space through randomized techniques. The main idea is that you can exploit concentration of measure to greatly reduce the dimension of the space while preserving distances up to tolerance $\epsilon$. In particular, following from the ...

4

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 is minimized. Kenneth J Supowit: "Topics in Computational Geometry" Ph.D. thesis, Dept. of Computer Science, University of Illinois at Urbana-Champaign (...

3

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)$-dimensional subspace $S(c)$ by restricting the three dimensions that correspond to the three variables in $c$. If a variable occurrs positively in $c$, then fix ...

3

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 case of e.g. sum or sum of squared distances to a shape or set of shapes (as PCA, linear regression or k-means) there is a generic reduction from eps-net to ...

3

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 probability $\geq 1-\epsilon^{O(1)}$ by the $\epsilon$-net theorem (well, more precisely the $\epsilon$-sample theorem). You can apply this to a polygon - you ...

3

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 quadtrees and octrees. K-d trees are used extensively in machine learning to speed up nearest-neighbor searches. If you squint just a little, decision trees also fit ...

3

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 algorithm whose clusters are not limited in radius. The problem is known to be NP-complete for $k\geq 2$. For unit balls, this problem has a PTAS ( ($1+\epsilon$)-...

3

What you want is to find the connected components of the intersection graph of the polygons, right? It would help to be more clear about what counts as an intersection: do the boundaries have to cross or does one polygon entirely inside another count as an intersection? And can the polygons have holes? Regardless, a natural lower bound for running times for ...

3

If you're okay with additional variables, then the answer is yes. This follows from Balas's extended formulation for the disjunction of polyhedra. It shows that $\operatorname{convex}.\operatorname{hull} ( \cup_j P_j)$ admits an extended formulation of size at most $\sum_{j}(\operatorname{xc}(P_j)+1)$, where $\operatorname{xc}(\cdot)$ denotes extension ...

3

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 bound drops to near quadratic. See the work by Koltun and Sharir, I think.

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