2
$\begingroup$

Assume I have a list of $N$ surfaces $\{S_i\}, i \in [1,N]$ which may or may not overlap.

I also have a boolean function $F(S_{i_1},\dots,S_{i_k})$ (with $1 \le k \le N$) which tests whether all surfaces $S_{i_k}$ overlap (or if they were discrete sets, then $F$ would test whether they contain a common element). In other terms: $F(\{S_{i_k}\})=\;\; (\;\cap_{j=1}^{k} S_{i_j} \;\;!=\;\;\emptyset \;)$.

I now consider the "set of maximum overlaps", $L_\rm{max}=\{O_1,\dots,O_m\}$, where each $O_j$ is a set with $n(j)$ elements being surfaces that all share a common intersection. More specifically: $O_j=\{S_{j_1},...S_{j_{n(j)}}\}$ with $\cap_{i=1}^{n(j)} S_{j_i} \ne \emptyset$ (or equivalently $F(O_j)=\rm{True}$).

$L_\rm{max}$ is unique once defined through the following two constraints that it must satisfy:

a) Each surface must appear in at least one overlapping set $O_i$ of $L_\rm{max}$.

b) Each overlapping set $O_i$ in $L_\rm{max}$ must be "maximal" in the sense that there cannot exist a surface $S_j$ not part of $O_i$ and for which its intersection with the intersection of all surfaces in $O_i$ is not empty.

One may write this definition of $L_\rm{max}$ more formally as follows:

$L_\rm{max} := \; \{ O_j \}\;\rm{with}\; O_j=\{S_{j_1}\dots S_{j_{n(j)}} \} \;|\;$

$\;\;\; \forall j \; \cap_{i=1}^{n(j)} S_{j_i} \ne \emptyset \;,$

$\;\;\; \forall i \; \exists\; j\; \rm{s.t.}\; S_i \in O_j\;,$

$\;\;\; \forall j \; \not\exists\; r\; \rm{s.t}\; (\; S_r \notin O_j \; \rm{and}\;S_r \cap (\cap_{i=1}^{n(j)} S_{j_i}) \ne \emptyset\;) $

Now, the problem is to identify the algorithm building $L_\rm{max}$ and requiring the least expected number of calls to the function $F$, assuming that any legal solution set $L$ is equally likely before the problem is investigated by successive calls to the function $F$.

The above sounds complicated but it is visually very simple to illustrate. I therefore include below a graphical representation of the problem for 5 surfaces (but please answer the abstract problem, not the particular realisation below): Example problem

In that example, the solution set $L_\rm{max}$ is:

$\{ \{S_1, S_2, S_3\},\; \{S_3, S_4\},\; \{S_5\} \}$

And here are some examples of the output of the function $F$:

$F(S_1, S_2)=\rm{True}$

$F(S_3, S_4)=\rm{True}$

$F(S_3, S_5)=\rm{False}$

$F(S_1, S_2, S_3)=\rm{True}$

$F(S_1, S_2, S_3, S_4)=\rm{False}$

$F(S_2, S_4)=\rm{False}$

$F(S_i)=\rm{True}, \forall i$

etc...

Note that I am curious as to what is the exact answer to this set-theoretic puzzle with no reference to the particularity of the example above (e.g. the surface $S_i$ could very well be discrete sets too). My hope is that someone may recognise this problem to be isomorphic to some other known mathematical problem with an established solution.

In practice however, my academic research would actually benefit from a solution tailored to the case of convex volumes (but with parametric equations of higher degree than quadratic and in an arbitrary number of dimension). In particular, I would be very interested if someone knows how to cast the derivation of the set $L_\rm{max}$ into a single convex-constrained optimisation problem.

Also, an algorithm proven optimal is of course not required, rather just an algorithm featuring a less disastrous complexity than the one of the naive implementation I came up with so far (which saturates around N=10 and I would need around N=100). Maybe this problem really is NP hard after all, but the question remains as to what is the algorithm of minimal expected complexity...

$\endgroup$
  • $\begingroup$ If I understood you right, then there can be multiple smallest solution, for example for sets $\{1, 2\}, \{2, 3\}, \{3, 4\}, \{4, 1\}$ size of the smallest solution is equal to 2 and you can split it in more then one way. $\endgroup$ – Szymon Stankiewicz Sep 26 at 16:23
  • $\begingroup$ Thank you for your suggestion. Indeed, my definition of the set of maximum overlaps is not the one I intended. I edited my question and corrected the definition of $L_\rm{maxl$ so that it is now indeed unique and the problem is well-posed. $\endgroup$ – Valentin Hirschi Sep 28 at 0:10
  • $\begingroup$ Unfortunately there could be as many as $N \choose {N/2}$ sets in $L_{\max}$: That's the maximum size of a Sperner family (a family of sets in which no set contains any other: see here for more). That means the output size is exponential in $N$, and I don't see a way to invoke your boolean test function fewer than $O(\text{output size})$ times. $\endgroup$ – j_random_hacker Sep 29 at 13:17
  • $\begingroup$ Thank you for the reference to Sperner family. This seems indeed like a concept very closely related to my problem. It now seems clear to me that this problem is indeed NP hard. However, it remains unclear to me what is the optimal sequence of calls to the test function $F$. Indeed, when calling $F(S_{i_1},\dots,S_{i_k})$ with a large $k$ (i.e. testing for the common intersection of many surfaces) one potentially gains a lot more information at once than with $k=2$ if the test is positive, which is however less likely. $\endgroup$ – Valentin Hirschi Sep 29 at 19:05
  • $\begingroup$ So clearly there must be an optimal way of building $L_{\rm max}$ with successive calls to $F$ with various number of arguments $k$ which optimally balances this trade-off between the amount of information gained by the intersection test and the likelyhood that it is positive as a function of the number of arguments $k$. An extreme illustration of this trade-off is that if all surfaces overlap, then you can solved the problem with a single call to $F$ with all surfaces in argument obviously. However, this test is always useless except in that complete overlap case. $\endgroup$ – Valentin Hirschi Sep 29 at 19:12

Your Answer

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

Browse other questions tagged or ask your own question.