Abstract: Determinantal point processes (DPPs) are distributions over sets of items that model diversity through algebraic arguments. In a sense, DPPs are the kernel machines of point processes. Their applications in machine learning include summary extraction or recommendation systems. Yet, the cost of sampling from a DPP is prohibitive in large-scale applications, which has triggered a research effort towards efficient approximate samplers. We build a novel MCMC-based approximate sampler, and we empirically demonstrate that it is more sample-efficient than previous approaches. Our sampler combines ideas from combinatorial geometry, linear programming and Monte Carlo methods, and leverages the ability of the hit-and-run MCMC kernel to efficiently move across convex bodies.