Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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:

alt text

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?

share|improve this question
About the second question. The collection of all countable unions and intersections of convex and co-convex sets is not a $\sigma$ algebra. As you point out, open balls are in this family, so if it was a $\sigma$-algebra then it would contain the Borel $\sigma$-algebra, but it clearly doesn't since you're only taking one level of countable unions/intersections. On the other hand, if you look at the smallest $\sigma$-algebra containing all compact convex sets, then this is the Borel $\sigma$-algebra since it contains the open (or closed) balls and compact convex sets are Borel. –  Pablo Shmerkin Aug 17 '12 at 9:11
Pablo, thanks. I have modified the question to indicate that the sets generate, rather than exhaust, the sigma algebra. In any case, it seems as though Michael understood what I meant and has settled the second question. –  Vidit Nanda Aug 17 '12 at 9:14
add comment

2 Answers

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)$.

share|improve this answer
add comment

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):
         Convex Deficiency Tree
One emphasis in this paper is on "well-formed Boolean expressions" for representing shapes.

share|improve this answer
This is extremely interesting work. Thank you for the reference! –  Vidit Nanda Aug 17 '12 at 19:57
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.