Polynomial spaces associated to a convex body $C$ in $({bf R}^+)^d$ have been the object of recent studies. In this work, we consider polynomial spaces associated to non-convex $C$. We develop some basic pluripotential theory including notions of $C-$extremal plurisubharmonic functions $V_{C,K}$ for $Ksubset {bf C}^d$ compact. Using this, we discuss Bernstein-Walsh type polynomial approximation results and asymptotics of random polynomials in this non-convex setting.