## Most efficient method for set intersection

Suppose I have two finite sets, $$A$$ and $$B$$, with arbitrarily large cardinalities, the ordered integral elements of which are determined by unique (and well defined) polynomial generating functions $$f:\mathbb{N}\rightarrow\mathbb{Z}$$ given by, say, $$f_1(x_i)$$ and $$f_2(x_j)$$, respectively. Assume, also, that $$A\cap B$$ is always a singleton set $$\{a\}$$ such that $$a=f_1(x_i)=f_2(x_j)$$ where I’ve proven that $$i\neq j$$.

Assuming you can even avoid the memory-dump problem, it seems the worst way to find $$\{a\}$$ is to generate both sets and then check for the intersection. I wrote a simple code in Sagemath that does this, and, as I suspected, it doesn’t work well for sets with even moderately large cardinalities.

Is there a better way to (program a computer to) find the intersection of two sets, or is it just as hopeless (from a time-complexity perspective) as trying to solve $$f_1(x_i)=f_2(x_j)$$ directly when the cardinalities are prohibitively large? Is there a parallel-computing possibility? If not, perhaps there’s a way to limit the atomistic search based on a range of values—i.e., each loop terminates the search after it finds the first $$i$$ value such that $$f_1(x_i)>f_2(x_j)$$, knowing that $$f_1(x_{i+1}), f_1(x_{i+2}), f_1(x_{i+3}), \cdots, f_1(x_{i+n})>f_1(x_i)>f_2(x_j)$$.

Posted on Categories proxies

## determining decidability with intersection of context free languages

I am trying to solve this problem: Given context-free languages A, B, and C find if the language $$(A\cap B)\cup (B\cap C)$$ is empty. Is this problem decidable.

I know the CFG is not closed under intersection so we do not know that $$A\cap B$$ is also CFG. If it was CFG, I know how to prove decidability. Since we can’t determine about $$A\cap B$$, is there a way to prove whether or not this is decidable?

Posted on Categories proxies

## Finding $l$ subsets such that their intersection has less or equal than $k$ elements NP-complete or in P?

I have a set $$M$$, subsets $$L_1,…,L_m$$ and natural numbers $$k,l\leq m$$.

The problem is:

Are there l unique indices $$1\leq i_1,…,i_l\leq m$$, such that

$$\hspace{5cm}\left|\bigcap_{j=1}^{l} L_{i_{j}}\right| \leq k$$

Now my question is whether this problem is $$NP$$-complete or not. What irritates me is the two constraints $$l$$ and $$k$$ because the NP-complete problems that were conceptually close to it that I took a look on (set cover, vertex cover) only have one constraint respectively that also appears in this problem.

I then tried to write a polynomial time algorithm that looks at which of the sets $$L_1,…,L_m$$ share more than $$k$$ elements with other sets but even if all sets would share more than $$k$$ elements with other this wouldn’t mean that their intersection has more than $$k$$ elements…

This question kind of comes close but in it there is no restriction on the amount of subsets to use and the size of the intersection should be exactly $$k$$, but maybe this could be useful anyways.

Can somebody further enlighten me ?

Posted on Categories proxies

## How to conceive a Turing machine that is the intersection of the languages of two Turing machines?

We have $$M = (Q,Σ,Γ,δ,q_0,q_a,q_r)$$ and $$M′= (Q′, Σ , Γ′, δ′,q_0′,q_a′,q_r′)$$.

We want to construct a standard Tm that recognize L(M) ∩ L(M′). How do I go about it? I don’t have much more information than this. Anything to get started would be appreciated.

Posted on Categories proxies

## Intersection of line segments induced by point sets from fixed geometry

I am reading up on algorithms and at the moment looking at the below problem from Jeff Erickson’s book Algorithms. I solved (a) by seeing a relationship to the previous problem on computing the number of array inversions. However, I am struggling with problem (b) as I cannot see how to reduce the circle point arrangement to an arrangement of points and lines that would be an input to the problem posed in (a). Assuming I have something for (b), I also cannot see how one might resolve (c).

For part (b), clearly every point $$p = (x, y)$$ satisfies $$x^2 + y^2 = 1$$ but I do not see how I might be able to use this fact to do the reduction. The runtime I am shooting for of $$O(n \log^2 n)$$ also seems to tell me the reduction is going to cost something non-trivial to do.

Can anyone have some further hints/insights that might help with part (b) and potentially even part (c)?

Posted on Categories proxies

## Is the emptiness of intersection of two CFLs decidable?

Consider $$L = \{\langle L_1, L_2\rangle\mid L_1, L_2 \in \text{CFL} \text{ and } L_1 \cap L_2 = \emptyset \}$$. How to prove that $$L \notin R$$?

$$L_1, L_2$$ encoded in chomsky-normal-form.

Posted on Categories proxies

## Is the BPP class closed for union and intersection?

Just like the title says. I want to prove that given two languages $$L_1,L_2 \in BPP$$, $$L_1 \cup L_2 \in BPP$$ and $$L_1 \cap L_2 \in BPP$$

## Algorithm for intersection point between two vectors

I’m trying to learn Computational Geometry and this formula isn’t obvious to me.
Hint: "cross" is related to the cross product of two vectors .

// returns intersection of infinite lines ab and pq (undefined if they are parallel)     point intersect(center code hereonst point &a, const point &b, const point &p, const point &q)     {         double d1 = cross(p - a, b - a);         double d2 = cross(q - a, b - a);         return (d1 * q - d2 * p) / (d1 - d2);     } 
Posted on Categories proxies

## 3D intersection algorithm for cylinders

The problem

Input is a list of $$N$$ cylinders in 3D space, and output should be a list of $$M≤N(N-1)/2$$ pairs of cylinders that intersect. ($$M$$ depends on input data, obviously.)

If it matters, the cylinders are very thin (diameter less than 1% of the length for all cylinders), and a solution for “rounded cylinders” would work for me (it probably simplifies the geometry calculations). A “rounded cylinder” is a cylinder with half-spheres at the extremities; formally, for a start point $$S$$, an endpoint $$E$$ and a radius $$r$$, the rounded cylinder $$(S, E, r)$$ is defined as the set $$\{P|∃ Q ∈ [S,E], ||PQ|| ≤ r\}$$.

The obvious solution

It is easy enough to do in $$O(N^2)$$ time and $$O(max(M, N))$$ space: the pseudocode of my current implementation is (for rounded cylinders):

Ncyl = length(cylinder_list) output = {} for i = 1, 2, ... Ncyl:   for j = i+1, i+2, ... Ncyl:     (S1, E1, r1) = cylinder_list[i]     (S2, E2, r2) = cylinder_list[j]     find P∈[S1, E1], Q∈[S2, E2] such that ||PQ|| is minimal  # this is the costly line, says the profiler     if ||PQ|| < r1 + r2:       add (i, j) to output return output 

Better performance?

Any algorithm will have a (time and space) worst-case in $$O(N^2)$$ (at least) because the output list can itself be of that length. However, the above algorithm guarantees $$O(N^2)$$ time even on “friendly” data because it tests all possible intersections.

In my use case, the cylinders are fairly spread apart in space (the longest cylinder is less than one tenth of the diameter of the whole set of cylinders). Furthermore, they occupy a small fraction of space and $$M\sim N$$ (for values of $$N$$ up to 2000 or so, above that it times out). This suggests to me that there could be an improvement by some “sweeping plane” algorithm similar to Bentley-Ottmann. However, I did not find a straightforward way to do Bentley-Ottmann in 3D (in 2D after sweeping you end up ordering points on a line which is easy enough, but in 3D there is no obvious ordering for a plane).

Posted on Categories proxies

## Maximizing integer sets intersection (with integer delta)

There are two sets of integers with different numbers of items in them.

X= { x_0, x_1, ... x_n }, x_0 < x_1 < ... < x_n Y= { y_0, y_1, ... y_m }, y_0 < y_1 < ... < y_m 

And there is a function of a single integer defined as

F(delta) = CountOfItems( Intersection( X, { y_0+delta, y_1+delta, ... y_m+delta) ) ) 

That is – i add delta integer to every element of the Y and then count how many same integers are in the X and the modified Y.

And then the problem – find delta that maximizes F(delta).

max( F(delta) ), where delta is integer 

Is there some “mathematical” name for such task and optimal algorithm for this? Obviously i can use brute-force here and enumerate all possible combination – but it does not work for big n and m.

Posted on Categories proxies