Chapter 2, Section 2.5 of Computational Geometry in C (1998), accessible via Google books,
is on this topic: "Convex Partitioning."
There are several choices here:
(1) Triangulation, which always results in $n-2$ pieces for a polygon of $n$ vertices;
(2) the Hertel-Mehlhorn algorithm, which is never worse than $2r+1$ pieces, where $r$ is the number of reflex vertices (which means it is never worse than four times the minimum);
or (3) Chazelle's complex cubic algorithm that finds the minimum partition.
The H-M algorithm is a happy medium in terms of both implementation difficulty (easy) and quality of result (not bad).
There is a 4th choice if you insist that the corners of all your convex pieces are subsets of the polygon's vertices (unlike the example above).
Then Greene's (now) cubic dynamic programming algorithm achieves the minimum number of pieces.
Both Greene's algorithm and the Hertel-Mehlhorn algorithm are implemented in CGAL; see the "2D Polygon Partitioning" section of the CGAL manual.
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.
Best Answer
[Let me put this in a separate answer, despite Gerhard's kind invitation :-), as I would like to de-emphasize seeking efficiencies.]
It might not be worth using a divide-and-conquer scheme, which could lead to implementation complexities. My inclination, as I mentioned in a comment, is to just incrementally clip: at any point, intersect the polygon for the first $k$ halfplanes with the $(k+1)$-st halfplane. Even if you have $n=10^9$ halfplanes, it is likely the intersection will grow as $\log n$, which is the growth-rate of the convex hull of points drawn from a uniform distribution (an old result of Dwyer). So you would still get $O(n \log n)$ performance with a naive worstcase $O(n^2)$ algorithm.
If you still want efficiencies:
Maintain a bounding box for each intermediate convex polygon for quick rejection of superfluous clips.
Use an efficient data structure to store the intermediate convex polygons so that the cutting can be achieved by binary search.
Choose carefully among the highly optimized line-clipping algorithms developed by the graphics community over the years.
Finally, "arrange the cuts so that the pieces obtained have very few sides" (to quote Gerhard); but I don't see how to do that in a way that might not cost more than the savings.