How do I recover a convex region from the set of its tangent planes? Let $S\subset\mathbb R^n$ a convex region, and suppose we know how to characterise this region in terms of its tangent planes. Explicitly, this means that, for every direction $\hat n_\theta\in S^{n-1}$, we know that all the points $x\in S$ satisfy
$$\langle \hat n_\theta, \boldsymbol x\rangle\le M(\theta)$$
for some known function $M(\theta)$. Moreover, we know that this inequality is tight (and so there is some point in $S$ which saturates it).
How can we go from this description to an algebraic description for the surface?

As a simple example in $\mathbb R^2$, suppose $S$ is a circle, but we don't know this. Instead, we only know that it is a region such that, for every direction $\hat n_\theta$, it lies below a given plane. We can visualise this as follows:


where the green arrow represents the directions $\hat n_\theta$, and the blue line is given algebraically for each angle $\theta$ by
$\cos(\theta) (x-x_0)+\sin(\theta)(y-y_0)= r,$
where $x_0,y_0,r$ are the coordinates of the center of the circle and its radius, respectively.
The function $M(\theta)$ is thus, in this case, given by $M(\theta)=\cos(\theta) x_0 + \sin(\theta) y_0 + r$.
How do I use this $M(\theta)$ to retrieve an algebraic characterisation for the region, which in this toy example would be $(x-x_0)^2+(y-y_0)^2=r^2$?
 A: I believe the answer to be the parametric curve $(x(\theta), y(\theta))$ given by $$x(\theta) = M(\theta)cos(\theta) - M^{'}(\theta)  sin(\theta)$$
$$y(\theta) = M(\theta)sin(\theta) + M^{'}(\theta) cos(\theta)$$
I've tried computing a proof but in the end I've gotten it with an informal sketch. 

A: Here is my elaboration of the suggestions given in the comments and answers.
$\newcommand{\ntheta}{\hat n_\theta}$Let $A\subseteq \mathbb R^n$ be our convex closed (finite) region. What we know about this region is that, for all $\mathbf x\in A$ and direction $\ntheta\in S^{n-1}$, there is some $M(\theta)$ such that
$$\langle \ntheta,\mathbf x\rangle= M(\theta)\equiv\min\{C\ge0 : \forall \mathbf y\in A,\,\, \langle \ntheta,\mathbf y\rangle\le C\}.\tag A$$
In words, $M(\theta)$ is gives the location of the plane normal to $\ntheta$ that touches $A$.
The problem is to go from the knowledge of $M(\theta)$ in (A), to a full characterisation of the region $A$.
The main observation is that we can think of $F(\theta)\equiv M(\theta)-\langle\ntheta,\mathbf x\rangle=0$ as the constraint characterising $A$, and therefore observe that $F'(\theta)$ gives, for every $\theta$, the set of points orthogonal to $A$ at the point $\mathbf x$ such that $\langle \ntheta,\mathbf x\rangle= M(\theta)$. To recover $A$, we therefore just need to find the intersection between these points and the surface itself, that is, solve the system:
$$\begin{cases}
  \partial_\theta[M(\theta)-\langle\ntheta,\mathbf x\rangle]=0, \\
  M(\theta) = \langle\ntheta,\mathbf x\rangle.
\end{cases}\tag B$$
It's worth noting that this will not have a solution for every $\theta$. Indeed, while $M(\theta)$ is always well-defined, there can in general be angles that do not correspond to any point of $\partial A$ (think for example what happens if $A$ is a triangle, in which case there are only three values of $\theta$ corresponding to planes tangent to $A$).
Here are a few examples of how this works:
Toy example with misplaced circle
Consider the region $A$ defined algebraically as $(x-x_0)^2+(y-y_0)^2=r^2$.
For any direction $\theta$, we can easily find that
$M(\theta)=\cos\theta x_0 + \sin\theta y_0 + r$.
In this case (B) thus reads
$$\begin{cases}
  -\sin\theta (x_0-x) + \cos\theta (y_0-y) = 0, \\
  \cos\theta (x_0-x) + \sin\theta (y_0-y) + r= 0,
\end{cases}$$
we thus find from the first equation $\theta=\theta(x,y)$ to be given by $\tan\theta = (y-y_0)/(x-x_0)$, which then using the second equation gives back the equation of the circle. The $\cos\theta=0$ case is also handled trivially.
More contrived example with discontinuities
Suppose now $A$ is the convex hull of the graph of $y=x^2$ in the domain $x\in[-1,1]$.
In this case, $M(\theta)$ is given by solving
$$M(\theta) = \max_{x\in[-1,1]} [x(\cos\theta + \sin\theta\, x)].$$
This is a bit tricky because the maximum is achieved sometimes at the boundary and sometimes in the inside of the region. The local stationary points are given by solving $\cos\theta+2x\sin\theta=0$, and thus correspond to the points
$x=-\frac12 \cot\theta$, whenever this is inside $[-1,1]$. One then has to check for each $\theta$ what the maximum is, which is a tedious but straightforward procedure, and finally leads to the result (as given by Mathematica, with a few simplifications):
$$M(\theta) = \begin{cases}
 1 & \theta\in\{0,\pi/2,\pi\} \\
 -\frac{1}{4} \cos (\theta ) \cot (\theta ) & \cos (\theta )>2 \sin (\theta )\land 2 \sin (\theta )+\cos (\theta )\leq 0 \\
 \sin (\theta )-\cos (\theta ) & (\cos (\theta )\leq 2 \sin (\theta )\land \sin (\theta )<0)\lor (\sin (\theta )>0\land \cos (\theta )<0) \\
 \sin (\theta )+\cos (\theta ) & (\sin (\theta )>0\land \cos (\theta )>0)\lor (\sin (\theta )<0\land 2 \sin (\theta )+\cos (\theta )>0).
\end{cases}$$
which looks like the following when plotted for $\theta\in[0,2\pi]$:

$\hskip2in$
The corresponding characterisation of the region can be represented as follows:
$\hskip2in$
Now the question is how to retrieve the original region from this. There are essentially two regions to consider: the smooth lower part of $A$, and the discontinuous upper regions.
The lower part corresponds to the angles such that $-2\arctan(2+\sqrt5)\le\theta\le 2\arctan(2-\sqrt5)$, for which $M(\theta)=-\frac14 \cos\theta\cot\theta$.
Here, system (A) becomes, using the simplified notation $\cos\theta\equiv c, \sin\theta\equiv s$, 
$$\begin{cases}
   c x + s y = -\frac14 c^2/s, \\
  -s x + c y = \frac{c}{4}(1+1/s^2).
\end{cases}$$
Solving this system we get
$$\begin{cases}
  x = \frac14 c/s[ -c^2 -s^2 - 1] = -\frac12 (c/s), \\
  y = \frac14[ -c^2 + c^2(1+1/s^2) ] = \frac14 (c/s)^2,
\end{cases}$$
which parametrises $y=x^2$ in the considered $\theta$ domain, as expected.
Consider now the set of angles in which $M(\theta)=\cos\theta+\sin\theta$.
Here, the system becomes
$$\begin{cases}
  c x + sy = c + s, \\
  \partial_\theta[c x + s y - (c+s)]
    = -s x + c y + s - c = 0,
\end{cases}$$
which solves to $x=y=1$ for all $\theta$s, again as expected from the figure.
The angles with $M(\theta)=-\cos\theta+\sin\theta$ are handled similarly, and give the solution $y=-x=1$.
The final case to handle is $\theta=\pi/2$.
This case is actually toughest, because $M'(\theta)$ is discontinuous at this point, and so we cannot use the usual system. This failure is most likely due to the non-injectivity of the mapping between $\mathbf x$ and corresponding angle $\theta$ (that is, the flat part of the region). A way around this is to simply connect the solutions found for the angles $\theta\neq\pi/2$, that is, $x=y=1$ and $y=-x=1$, with a straight segment (although in fairness I'm not sure how to formalise why this works).
Triangle
Another interesting example is one with a region that is the convex hull of a finite number of points. So let's consider a function $M(\theta)$ of the form
$$M(\theta) = \begin{cases}
  \cos\theta, &\theta\in[-\pi/2,\pi/4], \\
  \sin\theta, &\theta\in[\pi/4,\pi], \\
  0, &\theta\in[-\pi,-\pi/2].
\end{cases}$$
We have three regions to consider.
For $\theta\in[-\pi/2,\pi/4]$, we have
$$\begin{cases}
  -s x + c y = -s, \\
  c x + s y = c
\end{cases}$$
which solves to $x=1$ and $y=0$.
For $\theta\in[\pi/4,\pi]$, we have
$$\begin{cases}
  -s x + c y = c, \\
  c x + s y = s,
\end{cases}$$
which gives $x=0$ and $y=1$.
Finally, for $\theta\in[-\pi,-\pi/2]$, we have
$$\begin{cases}
  -s x + c y = 0, \\
  c x + s y = 0,
\end{cases}$$
and thus $x=y=0$.

$\hskip2in$
This tells us that the region must then be the convex closure of the three points $(1,0), (0,1), (0,0)$, that is, a right triangle (which is of course what I used to find $M(\theta)$ in the first place).
