The (Sigma) Algebra of Convex Sets

Question

This is a question-by-proxy for a colleague from computer science. I'm sure many people here are already aware that convex decomposition forms an important sub-field of both computational geometry and vision (in the CS sense). The prototypical problem in this field is as follows:

Consider a nice compact, connected set $B \subset \mathbb{R}^n$ with non-zero volume (this set is typically a polyhedron). Find a minimal collection of closed convex subsets $C_j \subset B$ such that the union of $C_j$'s equals $B$, and all pairwise intersections $C_i \cap C_j$ for $i \neq j$ have zero volume.

A lot of work has gone into this, presumably because convex objects are considered simpler to analyze than arbitrary compact blobs. I'm no expert in the field, but I believe it is quite standard: algorithms have been implemented in CGAL, based on Chazelle's pioneering work.

A lot of the theory breaks down almost immediately if one starts to step away from polyhedra. My question here can be best explained with this picture:

Note that there is no convex decomposition for the square minus disc on the left. So,

Which compact sets with non-zero volume are definable as finite unions and intersections of convex sets and their complements?

And of course, the natural follow-up: if we allow countable rather than finite unions and intersections and restrict our domain to some compact, convex subset of $\mathbb{R}^n$, then the definable sets naturally generate a sigma algebra.

Is this convex sigma algebra the same as the traditional one with open sets as a basis?

On one hand, every open ball is a countable union of closed convex subsets. But what about the other direction?

Answer 1

This is tangential to the posed question, not an answer. But there has been work on a discrete version of this concept, called in the literature the convex deficiency tree. For example, here is Fig. 1 from the paper, V. Shapiro, "A Convex Deficiency Tree Algorithm for Curved Polygons," International Journal of Computational Geometry & Applications, Vol. 11, No. 2 (2001) 215-238 (World Scientific link):
         
One emphasis in this paper is on "well-formed Boolean expressions" for representing shapes.

Answer 2

The answer to the second question is yes. Trivially, every closed convex set is closed and hence in the Borel $\sigma$-algebra as the complement of an open set.

For the other direction, note that every open or closed ball is convex. Every open ball is an incrasing union of closed balls. And every open set is a countable union of open balls, since $\mathbb{R}^n$ is separable.

If one wants to restrict the problem to a compact, convex subset of $\mathbb{R}^n$, one can use the fact that a trace $\sigma$-algebra is generated by the traces of generators. That is, if $(Y,\mathcal{Y})$ is a measurable space and $\mathcal{G}\subseteq 2^Y$ such that $\mathcal{Y}=\sigma(\mathcal{G})$, and $X\subseteq Y$, then the $\sigma$-algebra $\{B\cap X:B\in\mathcal{Y}\}$ equals $\sigma\big(\{X\cap G:G\in\mathcal{G}\}\big)$.