The Function VC

Function for verifying if a set G  is covered by a collection of sets P in the three dimensional real space.
Usage:
VC[G,P]
G....description of the set G as a list of single inequalities using x, y and z.
P....a list of sets. Each set must be given as a list of single inequalities using x, y and z.

All kinds of inequalities are allowed (<,≤,>,≥).
Single inequalities mens that expressions as 1<x<2 are forbidden and must be substituted by the two inequalities 1<x and x<2.
Equalities such as x=2 must by expressed by the inequalities x≤2 and x≥2.
The inequalities do not have to be linear in x,y,z, but the use of a lot of non-linear expressions slows down the algorithm extremely.
Only use rationals as numerical expressions.

The algorithm continuously  returns some information about the progress in %. These outputs are just rough reference values. The values do not correspond to the percentage of the run-time or the volume of G (With the present form of the algorithm this is quasi impossible). 

If G is fully covered by the sets of P, the argorithm will terminate without returning further output. If a subset of G is detected not to be fully covered, the algorithm will return this subset.

Examples:
VC[{x^2+y^2+z^2<1},
   {{x<1,x≥0,y<1,y≥0,z<1,z≥0},{x<1,x≥0,y<1,y≥0,z<0,z≥-1},{x<1,x≥0,y<0,y≥-1,z<1,z>=0},{x<0,x≥-1,y<1,y≥0,z<1,z≥0},
   {x<1,x≥0,y<0,y≥-1,z<0,z≥-1},{x<0,x>-1,y<1,y≥0,z<0,z≥-1},{x<0,x≥-1,y<0,y≥-1,z<1,z≥0},{x<0,x≥-1,y<0,y≥-1,z<0,z≥-1}}]
This call checks if the open unit ball is covered by half open 1×1×1 cubes (always a closed and an open side being opposite). Of course, these sets cover 
the unit ball and the algorithm yields no output.
VC[{x^2+y^2+z^2≤1},
   {{x<1,x≥0,y<1,y≥0,z<1,z≥0},{x<1,x≥0,y<1,y≥0,z<0,z≥-1},{x<1,x≥0,y<0,y≥-1,z<1,z>=0},{x<0,x≥-1,y<1,y≥0,z<1,z≥0},
   {x<1,x≥0,y<0,y≥-1,z<0,z≥-1},{x<0,x>-1,y<1,y≥0,z<0,z≥-1},{x<0,x≥-1,y<0,y≥-1,z<1,z≥0},{x<0,x≥-1,y<0,y≥-1,z<0,z≥-1}}]
This same call for the closed unit ball. Obviously three points are not covered and the program returns a set that includes these points.

$RecursionLimit = Infinity;
Off[General::spell1];

\(\(RL = 
        Function[inq, 
          Block[{in, i, 
              l}, 

 (*Removes\ redundant\ Inequalities\ of\ a\ system\ \((given\ either\ as\ List\ or\ linked\ with\ And)\)*) 
 (*In\ this\ context\ it\ gives\ clearer\ results\ as\ the\ built\ in\ command\ Reduce*) 

in = 
              List @@ inq; 
i = 1; 
l = 
              Length[in]; 
While[
              i ≤ l, 
in = 
                Complement[
                  in, {\((List @@ 
                          inq)\)[\([\)\(i\)\(]\)]}]; 
If[
                FindInstance[\((And @@ in)\) ∧ 
                      Not[\((List @@ inq)\)[\([\)\(i\)\(]\)]], {x, y, 
                      z}] ≠ {}, 
in = 
                  Append[in, \((List @@ 
                          inq)\)[\([\)\(i\)\(]\)]]]; 
\(i++\)]; 
Head[inq] @@ 
              in
]];\)
\)
RS = 
        Function[{Gs, 
            Ps}, 

 (*Chooses from list of periods those,  
            which intersect with a given set*)  

Select[
            Ps, (FindInstance[(And @@ Gs) ∧ (And @@ #), {x, y, 
                      z}] ≠ {}) &]];


\(\(VC = 
        Function[{GS, sets}, 
          Block[{ges, 
              VC1}, 

 (*Main\ Program . \ It\ calles\ the\ recursive\ main\ \(\(routine\)\(.\)\)*) 

VC1 = 
              Function[{$ModuleNumber, G, P}, 
                Block[{inq, 
                    i}, 

 (*Main\ recursive\ routine*) 

 (*A\ direct\ verification\ via\ FindInstance\ is\ useful\ only\ when\ the\ given\ set\ G\ intersects\ with\ at\ most\ 3\ sets\ \((otherwise\ it\ is\ too\ slow)\) . \ 
                        
                        Tests\ showed\ that\ the\ algorithm\ runs\ faster\ by\ verifying\ directly\ for\ at\ most\ 2\ sets*) 

\(If[
                      Length[P] ≤ 2, 
If[
                        FindInstance[\((And @@ G)\) ∧ 
                              Not[Or @@ \((\(\((And @@ #)\) &\) /@ P)\)], {x, 
                              y, z}] ≠ \ {}, 
                        Print["The subsetset ", 
                          And @@ 
                            G, " is not fully covered"]]; 
ges = 
                        ges + 2^\((\(-\(($ModuleNumber - 
                                    1)\)\))\); 
Print[
                        ges*100\  // 
                          N\ , "% done"], 

 (*Otherwise\ the\ first\ inequality\ that\ induces\ an\ intersection\ of\ G\ is\ taken\ to\ split*) \ 
 (*if\ there\ is\ no\ inequality\ left\ that\ splits\ G\ then\ G\ is\ \(\(covered\ !!\)!!\)*) 
inq = Union @@ P; 
i = 
                        1; 
While[\((i ≤ 
                              Length[inq])\) ∧ \((FindInstance[
                                And @@ G ∧ 
                                  Not[inq[\([\)\(i\)\(]\)]], {x, y, 
                                  z}] == {})\)\ , \(i++\)]; 
If\ [
                        i ≤ 
                          Length[inq], 
VC1[$ModuleNumber + 
                            1, RL[Append[G, inq[\([\)\(i\)\(]\)]]], 
                          RS[Append[G, inq[\([\)\(i\)\(]\)]], 
                            P]]; 
VC1[$ModuleNumber + 1, 
                          RL[Append[G, Not[inq[\([\)\(i\)\(]\)]]]], 
                          RS[Append[G, Not[inq[\([\)\(i\)\(]\)]]], 
                            P]], 
ges = 
                          ges + 2^\((\(-\(($ModuleNumber - 
                                      1)\)\))\); 
Print[
                          ges*100\  // 
                            N\ , "% done"]]];\)
]]; 

ges = 0; 
VC1[1, 
              List @@ GS, sets];
]];\)\)