Abstract Exhibiting a deep connection between purely geometric problems and real algebra, the complexity class $$\exists \mathbb {R}$$ ∃ R plays a crucial role in the study of geometric problems. Sometimes $$\exists \mathbb {R}$$ ∃ R is referred to as the ‘real analog’ of NP. While NP is a class of computational problems that deals with existentially quantified boolean variables, $$\exists \mathbb {R}$$ ∃ R deals with existentially quantified real variables. In analogy to $$\Pi _2^p$$ Π 2 p and $$\Sigma _2^p$$ Σ 2 p in the famous polynomial hierarchy, we study the complexity classes $$\forall \exists \mathbb {R}$$ ∀ ∃ R and $$ \exists \forall \mathbb {R}$$ ∃ ∀ R with real variables. Our main interest is the AreaUniversality problem, where we are given a plane graph G, and ask if for each assignment of areas to the inner faces of G, there exists a straight-line drawing of G realizing the assigned areas. We conjecture that AreaUniversality is $$\forall \exists \mathbb {R}$$ ∀ ∃ R -complete and support this conjecture by proving $$\exists \mathbb {R}$$ ∃ R - and $$\forall \exists \mathbb {R}$$ ∀ ∃ R -completeness of two variants of AreaUniversality. To this end, we introduce tools to prove $$\forall \exists \mathbb {R}$$ ∀ ∃ R -hardness and membership. Finally, we present geometric problems as candidates for $$\forall \exists \mathbb {R}$$ ∀ ∃ R -complete problems. These problems have connections to the concepts of imprecision, robustness, and extendability.

We show that the union of n translates of a convex body in $$\mathbb {R}^3$$ can have $$\varTheta (n^3)$$ holes in the worst case, where a hole in a set X is a connected component of $$\mathbb {R}^3 \setminus X$$ . This refutes a 20-year-old conjecture. As a consequence, we also obtain improved lower bounds on the complexity of motion planning problems and of Voronoi diagrams with convex distance functions.

We introduce combinatorial types of planar arrangements of convex bodies, extending order types of point sets to arrangements of convex bodies, and study their realization spaces. Our main results witness a trade-off between the combinatorial complexity of the bodies and the topological complexity of their realization space. First, we show that every combinatorial type is realizable and its realization space is contractible under mild assumptions. Second, we prove a universality theorem that says the restriction of the realization space to arrangements polygons with a bounded number of vertices can have the homotopy type of any primary semialgebraic set.

Given a polygonal region containing a target point (which we assume is the origin), it is not hard to see that there are two points on the perimeter that are antipodal, i.e., whose midpoint is the origin. We prove three generalizations of this fact. (1) For any polygon (or any bounded closed region with connected boundary) containing the origin, it is possible to place a given set of weights on the boundary so that their barycenter (center of mass) coincides with the origin, provided that the largest weight does not exceed the sum of the other weights. (2) On the boundary of any 3-dimensional bounded polyhedron containing the origin, there exist three points that form an equilateral triangle centered at the origin. (3) On the 1-skeleton of any 3-dimensional bounded convex polyhedron containing the origin, there exist three points whose center of mass coincides with the origin.