I've included an example of one such orthogonal pyramid. I would like to find a way to prove that this orthogonal pyramid can be partitioned by diagonals into convex quadrilaterals, and do so with an algorithm in linear time. My understanding is that a sweep-line algorithm from top to bottom would work well. However, I am not quite sure how to proceed with it.
Some additional info: An orthogonal polygon is a polygon in which each pair of adjacent edges meets orthogonally. An orthogonal pyramid (like the one pictured above) is an orthogonal polygon monotone with respect to the vertical that contains one horizontal edge (h in our case above) whose length is the sum of the lengths of all the other horizontal edges.