  Two well-known polytopes whose vertices are indexed by permutations in the
symmetric group $\mathfrak{S}_n$ are the permutohedron $P_n$ and the Birkhoff
polytope $B_n$. We consider polytopes $P_n(\Pi)$ and $B_n(\Pi)$, whose vertices
correspond to the permutations in $\mathfrak{S}_n$ avoiding a set of patterns
$\Pi$. For various choices of $\Pi$, we explore the Ehrhart polynomials and
$h^*$-vectors of these polytopes as well as other aspects of their
combinatorial structure.
  For $P_n(\Pi)$, we consider all subsets $\Pi \subseteq \mathfrak{S}_3$ and
are able to provide results in most cases. To illustrate, $P_n(123,132)$ is a
Pitman-Stanley polytope, the number of interior lattice points in
$P_n(132,312)$ is a derangement number, and the normalized volume of
$P_n(123,231,312)$ is the number of trees on $n$ vertices.
  The polytopes $B_n(\Pi)$ seem much more difficult to analyze, so we focus on
four particular choices of $\Pi$. First we show that the $B_n(231,321)$ is
exactly the Chan-Robbins-Yuen polytope. Next we prove that for any $\Pi$
containing $\{123,312\}$ we have $h^*(B_n(\Pi))=1$. Finally, we study
$B_n(132,312)$ and $\widetilde{B}_n(123)$, where the tilde indicates that we
choose vertices corresponding to alternating permutations avoiding the pattern
$123$. In both cases we use order complexes of posets and techniques from toric
algebra to construct regular, unimodular triangulations of the polytopes. The
posets involved turn out to be isomorphic to the lattices of Young diagrams
contained in a certain shape, and this permits us to give an exact expression
for the normalized volumes of the corresponding polytopes via the hook formula.
Finally, Stanley's theory of $(P,\omega)$-partitions allows us to show that
their $h^*$-vectors are symmetric and unimodal.
  Various questions and conjectures are presented throughout.
