Given a finite set $X = \{x_1,\dots,x_N\}$ of points in $\mathbb{R}^n$, let $V_j(X)$ be the interior of the Voronoi polytope corresponding to $x_j$, i.e., the interior of the set of points closer to $x_j$ than any of the other $x_k$.
Consider the map $V : X \mapsto V(X) = \{V(x_j)\}_{j=1}^N$ that sends $X$ to its Voronoi tessellation. Is there any known "interesting" characterization of the range of this map?
For what it's worth, this question was motivated by looking at a stone wall.
Although I am not sure I fully understand the question, perhaps this attempt at a partial answer will clarify matters.
First, it is known that every tree of at least one edge and with no vertices of degree $2$ can be realized as the Voronoi diagram of a set of points in convex position. See Ref.(1) below, from which this figure is taken:
Second, the general question of recognizing when a convex partition of the plane is a Voronoi diagram of some set of points was explored all the way back in 1985, Ref.(2) below, which solved it for the special case when all Voronoi vertices have degree 3. For the general, unrestricted case, recognition can be achieved in polynomial time via linear programming, Ref.(3).
But perhaps reducing the question to linear programming does not constitute an "interesting" characterization. I think the Ash-Bolker paper might include an interesting characterization, but I can't quite remember their argument...
(1) G. Liotta and H. Meijer, “Voronoi Drawings of Trees,” Comput. Geom. Theory and Appl., vol. 24, no. 3, pp. 147–178, 2003. (Journal link)
(2) P. Ash and E. Bolker, “Recognizing Dirichlet Tesselations,” Geometriae Dedicata, vol. 19, pp. 175–206, 1985.
(3) D. Hartvigsen, “Recognizing Voronoi Diagrams with Linear Programming,” ORSA J. Computing, vol. 4, no. 4, pp. 369–374, 1992. (Journal link)
