This is not a definitive answer, just some thoughts.
You start with a convex polygon $A$, and displace its vertices by a vector field to produce $B$,
connecting corresponding vertices. First, it is not clear that $B$ is necessarily a planar convex polygon, unless you have special conditions on the vector field. $B$ could be nonplanar; $B$ could be nonconvex. So the resulting polyhedron $P$ seems not well defined. You could define $P$ to be
the convex hull of $A$ and the vertices of $B$, but then you lose the property that each
vertex of $A$ is connected to its corresponding vertex in $B$.
Let me ignore this, and assume that $B$ is a planar convex polygon. Even for $A$ and $B$ triangles,
it may be that under one definition of what constitutes $P$, it is not tetrahedralizable.
The famous Schönhardt polyhedron is the simplest example:
Image from Discrete and Computational Geometry.
Setting aside both of these issues, which may not occur in your data, there are specialized
tetrahedralization algorithms. In fact, you might adapt the definition of $P$ so that
these algorithms apply.
Here is an incomplete tour through some literature.
Goodman and Pollack showed that the region between two convex polyhedra can be
tetrahedralized without "Steiner points," unlike the Schönhardt polyhedron.
Marshall Bern then showed that sometimes $\Omega(n^2)$ tetrahedra are needed:
(1) "Compatible tetrahedralizations," Marshall Bern,
Proceedings of the 9th Annual Symposium on Computational Geometry, 1993, pp.281-7.
Fundam. Inform., 1995: 371-384.
Two subsequent papers studied special cases that are easier: e.g., "slabs" in (2):
(2) "Tetrahedralization of Simple and Non-Simple Polyhedra,"
Godfried T. Toussaint, Clark Verbrugge, Cao An Wang, Binhai Zhu,
Canadian Conference on Computational Geometry, pp. 24-29, 1993.
and
a slightly more general case in (3) below.
I think this work by Palios may be the most relevant for your purposes, because
the case he considers can cover a version of your polyhedra $P$, and because
he proves that only $O(n)$ tetrahedra are needed in this case:
(3) Leonidas Palios,
"Optimal tetrahedralization of the 3D-region “between” a convex polyhedron and a convex polygon,"
Computational Geometry,
Volume 6, Issue 5, September 1996, Pages 263-276.
Once you have $P$ tetrahedralized, then you can focus on intersecting the tetrahedra with
the convex polyhedron.
Here is one relevant result, by Michael Hoffmann,
"Covering polygons with few rectangles," 2001. (PDF download link)
He shows that minimal covering by two or three congruent axis-aligned rectangles of a collection
of polygons with a total of $n$ vertices
can be found in $O(n)$ time.
He also says that the more general problem—covering a set of polygons by $p>3$ congruent rectangles—cannot
be approximated by better than a factor of $2$ unless $P=NP$
(because of the relation to the $p$-center problem).
He does not directly address covering just one polygon, or with covering by incongruent rectangles.
This latter problem (your problem) is partially addressed computationally in the paper 2011,
"Covering a polygonal region by rectangles,"
Computational Optimization and Applications
(Springer link). It appears that they
start with a set of rectangles, and extend them until they form a cover.
Best Answer
I haven't worked out the details but this seems very likely to be NP-complete. The reduction I have in mind uses the following ideas:
You can arrange three convex holes in such a way that the lines that separate one hole from another are very tightly constrained, so that it's not possible to separate all three pairs of holes from each other by three lines that meet in a single point. When this happens, it forces any partition into convex sets to include a fourth convex set (above the three convex sets containing the three holes), in the middle area between the three holes.
With a little more care you can set up systems of four holes, with two roughly-triangular areas loosely surrounded by three of the four holes, in such a way that you are forced to include a fifth convex set (above the four convex sets containing the four holes) in one of these two triangular areas, but you get to choose which of the two triangular areas to put the fifth convex set into.
Minimum dominating set is NP-complete for planar graphs, even if all vertices have degree at most three and even if there is some $k$ such that all degree-three vertices are separated from each other by paths of length at least $k$ (this is because subdividing edges into long paths of odd length changes the dominating set size in a predictable way). Using the four-hole gadgets described above to represent edges, it should be possible to reduce this special planar dominating set problem to your problem.