In the discrete k-Center problem, we are given a metric space (P, dist) where |P | = n and the goal is to select a set C ? P of k centers which minimizes the maximum distance of a point in P from its nearest center. For any ? > 0, Agarwal and Procopiuc [SODA'98, Algorithmica'02] designed an (1 + ?)-approximation algorithm1 for this problem in d-dimensional Euclidean space2 which runs in O(dn log k) + ( k? )O(k1-1/d) · nO(1) time. In this paper we show that their algorithm is essentially optimal: if for some d = 2 and some computable function f, there is an f(k)· ( 1? )o(k1-1/d) ·no(k1-1/d) time algorithm for (1 + ?)-approximating the discrete k-Center on n points in d-dimensional Euclidean space then the Exponential Time Hypothesis (ETH) fails. We obtain our lower bound by designing a gap reduction from a d-dimensional constraint satisfaction problem (CSP) to discrete d-dimensional k-Center. This reduction has the property that there is a fixed value ? (depending on the CSP) such that the optimal radius of k-Center instances corresponding to satisfiable and unsatisfiable instances of the CSP is < 1 and = (1 + ?) respectively. Our claimed lower bound on the running time for approximating discrete k-Center in d-dimensions then follows from the lower bound due to Marx and Sidiropoulos [SoCG'14] for checking the satisfiability of the aforementioned d-dimensional CSP. As a byproduct of our reduction, we also obtain that the exact algorithm of Agarwal and Procopiuc [SODA'98, Algorithmica'02] which runs in nO(d·k1-1/d) time for discrete k-Center on n points in d-dimensional Euclidean space is asymptotically optimal. Formally, we show that if for some d = 2 and some computable function f, there is an f(k) · no(k1-1/d) time exact algorithm for the discrete k-Center problem on n points in d-dimensional Euclidean space then the Exponential Time Hypothesis (ETH) fails. Previously, such a lower bound was only known for d = 2 and was implicit in the work of Marx [IWPEC'06]. © Rajesh Chitnis and Nitin Saurabh; licensed under Creative Commons License CC-BY 4.0