Kernel functions are a powerful tool to enhance the $k$-means clustering\nalgorithm via the kernel trick. It is known that the parameters of the chosen\nkernel function can have a dramatic impact on the result. In supervised\nsettings, these can be tuned via cross-validation, but for clustering this is\nnot straightforward and heuristics are usually employed. In this paper we study\nthe impact of kernel parameters on kernel $k$-means. In particular, we derive a\nlower bound, tight up to constant factors, below which the parameter of the RBF\nkernel will render kernel $k$-means meaningless. We argue that grid search can\nbe ineffective for hyperparameter search in this context and propose an\nalternative algorithm for this purpose. In addition, we offer an efficient\nimplementation based on fast approximate exponentiation with provable quality\nguarantees. Our experimental results demonstrate the ability of our method to\nefficiently reveal a rich and useful set of hyperparameter values.\n