I am developing a tool of curve manipulation. The core procedure is to calculate:

$$(a_1 \cup a_2 \cup \cdots \cup a_p) \cap (a_2 \cup a_3 \cup \cdots \cup a_{p+1}) \cap \cdots \cap (a_{n-p+1} \cup a_{n-p+2} \cup \cdots \cup a_n)$$

where $n$ and $p$ are both positive integers and satisfy $1 \lt p \lt n$ . However in this case, union and intersection operators are very time-consuming, so I need to simplify the formula for the fewest union / intersection symbols.

The aforementioned expression includes $(n-p+1)p$ times of union / intersection, which is $O(np)$ in complexity. I'm looking for a better solution.


This is not an answer.

First, how do you calculate $(n-p+1)(p-1)$? $p-1$ is number of unions in each bracket and there is $n-p+1$ brackets. So $(n-p+1)(p-1)$ is the number of unions. The number of intersections is $n-p+1$, hence $(n-p+1)p$? ... Just checking is I understand properly.

Your problem seems to simplify when you use distributive laws $$\begin{aligned} A\cup(B\cap C)&=(A\cup B)\cap(A\cup C)\\% A\cap(B\cup C)&=(A\cap B)\cup(A\cap C)\\% \end{aligned}$$ Using the former, as an example, you have $(a_{1}\cup a_{2})\cap(a_{2}\cup a_{3})=a_{2}\cup(a_{1}\cap a_{3})$ which saves one operation. $$\begin{aligned} (a_{1}\cup a_{2}\cup a_{3})\cap(a_{2}\cup a_{3}\cup a_{4})&=(a_{2}\cup a_{3})\cup(a_{1}\cap a_{4})\\ (a_{1}\cup a_{2}\cup a_{3})\cap(a_{2}\cup a_{3}\cup a_{4})&=a_{2}\cup((a_{1}\cup a_{3})\cap(a_{3}\cup a_{4}))\\ \end{aligned}$$ saves two and one respectively.

Applying this logic to a general version of your problem is probably slightly messy. Can you do significantly better using other information about your problem?

idea 1: Do you know anything about size of $a_{i}$ as $i$ varies (say your $a_{i}$ getting larger/smaller)? Why? My sense is that the bigger the sets involved, the more time to complete an operation. Then you want to prioritize approach that 'does intersections on the large sets' early on.

idea 2: Even if you do not know anything about size of $a_{i}$, I think you want to aim for an approach that does intersections as early as possible, since this simplifies the subsequent operations.

  • $\begingroup$ Yes you are right. I forgot to count the intersections. $\endgroup$ – Keyu Gan Feb 27 '17 at 15:30
  • $\begingroup$ @KeyuGan No problem, it was more of a check if I understand correctly. $\endgroup$ – Jan Feb 27 '17 at 15:33
  • $\begingroup$ a represents a planar region defined by a single polygon. I'm not good at computational geometry, though. So probably it is better for me to optimize the case in a more abstract way. $\endgroup$ – Keyu Gan Feb 27 '17 at 15:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.